AbuElias's blog

By AbuElias, history, 7 months ago, In English

i was solving this problem and i noticed that when i create a frequency array of sorted list its much faster than doing it on a unsorted list

this is my submession with sorted, when i submit the same code without sorting it gives TL.

then i noticed that when i loop on a sorted list is much faster than looping on a unsorted list with the same elements

`

import time import random

x = [] counter =1 a = 0 for i in range(10**6):

x.append(counter)

a+=1

if a == 2:

    a=0

    counter +=1

x = random.sample(x,len(x))

now = time.time()

freq1 = {}

for i in x:pass

print("done 1")

print(time.time() — now)

print("-----------")

x = sorted(x)

now = time.time()

freq1 = {}

for i in x:pass

print("done 2")

print(time.time() — now) ~~~~~

` ~~~~~

it prints

done 1

0.16895198822021484

done 2

0.012014389038085938

the first number is the time of looping on the list while its unsorted and the second one is the time after sorting

can any one explain why this happens

  • Vote: I like it
  • -2
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Namika (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Namika (previous revision, new revision, compare).

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why sorted is faster then unsorted https://rickystewart.wordpress.com/2013/09/03/why-sorting-an-array-makes-a-python-loop-faster/

Why your TLed solution actually can't pass https://codeforces.net/blog/entry/101817

Don't forget that you don't include sorting time here, so sort+iterate will be actually slower in reality. Time including sort on my machine:

done 1
0.16502690315246582
-----------
done 2
0.6931509971618652