Алгоритм вычисления «начальных списков» в O (m * log m) - PullRequest
Новая
       32

Алгоритм вычисления «начальных списков» в O (m * log m)

0 голосов
/ 24 мая 2018

Цель состоит в том, чтобы написать алгоритм, который вычисляет «начальные списки» (структуру данных) в классе сложности лучше, чем O (m ^ 2)

Что такое начальный список?

Пусть U будет набором кортежей (например, {(2,5), (5,1), (9,0), (6,4)}).

Шаг 1:

L1 упорядочен по первому элементу кортежа: 

L1 = [ (2,5), (5,1), (6,4), (9,0) ]

и L2 по второму: 

L2 = [ (9,0), (5,1), (6,4), (2,5) ]

Шаг 2:

Добавьте индексы кортежа e во втором списке к кортежу e в первом списке: 

L1 = [ (2,5,3), (5,1,1), (6,4,2), (9,0,0) ]

и наоборот: 

L2 = [ (9,0,3), (5,1,1), (6,4,2), (2,5,0) ]

L1 и L2 теперь называются начальными списками U.

Первая идея реализации, конечно, является исчерпывающим алгоритмом в O (m ^ 2) 

U = {(2,5), (5,1), (9,0), (6,4)}

m = len(U)

#step 1:
L1 = [e for e in U]
L1.sort()
L2 = [e for e in U]
L2.sort(key=lambda tup: tup[1])

#step 2:
help = []*len(L1)
for i in range(len(L1)):
    help[i] = L1[i][0], L1[i][1], L2.index(L1[i])

for i in range(len(L2)):
    L2[i] = L2[i][0], L2[i][1], L1.index(L2[i])

L1 = help

# >>> L1
# [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
# >>> L2
# [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]

Так что это работает.Но вызов индекса (O (m)) в цикле for (O (m)) делает его сложность квадратичной.Но как написать алгоритм для этого в O (m * log m)?

Ответы [ 2 ]

0 голосов
/ 24 мая 2018

Я вижу место для некоторой оптимизации здесь.

  • Сортируйте дважды, как раньше, но создайте два словаря для поиска индекса (это линейно по времени).
  • Вы также можете использовать operator.itemgetter для удаления лямбд.
  • Вы также можете отказаться от копирования вызовов, они не нужны, когда вы звоните sorted, так как sorted возвращает копию ваших данных. 

from operator import itemgetter
ip = {(2,5), (5,1), (9,0), (6,4)}

# step 1 - sort `ip` and create L1
L1 = sorted(ip)
# step 2 - create index lookup for L2
idx_L1 = {k : v for v, k in enumerate(L1)}

# step 3, 4 - repeat for L2
L2 = sorted(ip, key=itemgetter(1))
idx_L2 = {k : v for v, k in enumerate(L2)}

# step 5 - augment L1 and L2 with respective indexes from other lists
L1 = [(*x, idx_L2[x]) for x in L1]   # starred unpacking - python3.6+ syntax
L2 = [(*x, idx_L1[x]) for x in L2]   # use `x + (idx_L2[x],)` for older versions


>>> L1
[(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]    
>>> L2
[(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]
0 голосов
/ 24 мая 2018

Да.Одна возможность в O (m * log m) - просто сортировка 3 раза.Функция сортировки List.sort () - это O (m * log m) в Python: 

from copy import deepcopy

U = {(2,5), (5,1), (9,0), (6,4)}
m = len(U)

h = sorted(U) #O(m * log m)
for i in range(len(h)): #O(m)
  (u,v) = h[i]
  h[i] = (u,v,i)
h.sort(key=lambda tup: tup[1]) #O(m * log m)

L1 = deepcopy(h)
L2 = h

for i in range(len(L1)): #O(m)
  (u,v,_) = L1[i]
  L1[i] = (u,v,i) #reset indices i
L1.sort() #O(m * log m)

print(L1)
print(L2)

# [(2, 5, 3), (5, 1, 1), (6, 4, 2), (9, 0, 0)]
# [(9, 0, 3), (5, 1, 1), (6, 4, 2), (2, 5, 0)]
...