#!/usr/bin/env python
# -*- coding: utf-8 -*-

from __future__ import absolute_import, division, print_function, unicode_literals

import random
import math
import time

def main():
    arr_size = 100000
    # generate
    arr = []
    for i in xrange(0, arr_size):
        #arr.append(round(random.gauss(5, 0.85), 0))
        arr.append(i // 16)
    arr.sort()
    #print('array:')
    #print(arr)

    # O(n)
    t1 = time.time()
    frq0 = {}
    for i in arr:
        if i in frq0:
            frq0[i] += 1
        else:
            frq0[i] = 1
    t2 = time.time()
    print('frq O(n):')
    #print(sorted(frq0.iteritems()))
    print('length: %d' % len(frq0))
    print('time: %.3f' % (t2 - t1))

    ## O(sqrt(n))
    #t1 = time.time()
    #frq = {}
    #left_k = 0
    #while left_k < arr_size:
    #    left_v = arr[left_k]
    #    width = arr_size - 1 - left_k
    #    step = int(math.sqrt(width))
    #    #step = rsqrt(width)
    #    step = step if step else 1
    #    big_probe = left_k
    #    big_probe += step
    #    while big_probe < arr_size:
    #        if arr[big_probe] != left_v:
    #            break
    #        big_probe += step
    #    small_probe = big_probe - step
    #    while small_probe < arr_size:
    #        if arr[small_probe] != left_v:
    #            break
    #        small_probe += 1
    #    frq[left_v] = (small_probe - left_k)
    #    if left_k == small_probe:
    #        print('// hm...')
    #        break
    #    left_k = small_probe
    #t2 = time.time()
    #print('frq O(sqrt(n)):')
    #print(sorted(frq.iteritems()))
    #print('time: %.3f' % (t2 - t1))

    ## O(хер_знает_солько)
    t1 = time.time()
    frq = {}
    left_k = 0
    while left_k < arr_size:
        left_v = arr[left_k]
        step = 1
        probe = left_k + step
        while True:
            if step == 1:
                if probe == arr_size or arr[probe] != left_v:
                    break
            if probe >= arr_size or arr[probe] != left_v:
                probe -= step
                step = 1
                probe += step
                continue
            step *= 2
            probe += step
        frq[left_v] = probe - left_k
        left_k = probe
    t2 = time.time()
    print('frq O(хер_знает_сколько):')
    #print(sorted(frq.iteritems()))
    print('time: %.3f' % (t2 - t1))

if __name__ == '__main__':
    main()