Как оптимизировать агрегацию больших списков - PullRequest
Новая
       9

Как оптимизировать агрегацию больших списков

1 голос
/ 12 апреля 2019

Я хочу агрегировать баллы по пунктам
пункт будет отображаться в другом списке. и список является рангом. на основе местоположения предмета в другом списке получить другой результат

когда список ranked_items огромен. Как 1000 (список) * 1000 (элементы), цикл будет слишком длинным. Есть ли другое решение этой проблемы

Я попытался оптимизировать python.below это простая версия для легкого понимания

Я надеюсь, что из коробки выпрыгнет другое решение. Используйте другой способ решения этой проблемы 

'''
there are some list of ranked items
each list has a,b,c,d on different rank
'''
ranked_items = [
  ['a','b','c','d'],
  ['b','c','a','d'],
  ['d','c','b','a']
]

'''
base on item location in the list
the first location has score 0.9
the second location has score 0.7
'''
base_score = {
  0:0.9,
  1:0.7,
  2:0.5,
  3:0.3
}

'''
sum total score of each item
eg: 'a' in the first list first location then score is 0.9
in the second list third location then score is 0.5
the third list last location then score is 0.3
add them all.'a' final score is 1.7
'''
final_score = {}
for single_rank in ranked_items:
  for idx,item in enumerate(single_rank):
    final_score[item] = final_score.get(item,0) + base_score[idx]

#sort by score
final_score_sorted = sorted(final_score.items(),key=lambda kv: kv[1],reverse=True)

print(final_score_sorted)

'''
output
[('b', 2.1), ('c', 1.9), ('a', 1.7), ('d', 1.5)]
'''

и ranked_items может использовать другой формат
Вот пример формата списка 1D 

ranked_items = [
    ('a',0),
    ('b',1),
    ('c',2),
    ('d',3),

    ('b',0),
    ('c',1),
    ('a',2),
    ('d',3),

    ('d',0),
    ('c',1),
    ('b',2),
    ('a',3)
]

1 Ответ

0 голосов
/ 12 апреля 2019

Если ranked_items предоставляется в виде 2D-списка, мало что можно сделать, чтобы улучшить сложность среды выполнения, поскольку вам необходимо хотя бы один раз просмотреть 2D-список, чтобы прочитать данные.

То есть, по моему скромному мнению, лучшей возможной сложностью здесь будет O (N ^ 2) (учитывая N = len ([a, b, c, d])).

Для представленного 1D варианта , Видите ли, чтобы получить какой-либо результат, необходимо прочитать весь список хотя бы один раз. Давайте назовем длину одномерного списка М. Итак, наилучшей возможной сложностью будет O (M).

Обратите внимание, что это не улучшение по сравнению с последним подходом, так как M = N ^ 2, где N - длина дочерних списков в 2D представлении. Итак, O (M) = O (N ^ 2). Вы не можете сделать лучше, чем это.

...