Как быстро отсортировать dict () с огромным количеством ключей?

Question

TLE всегда происходит в SBANK SPOJ с использованием Python. Чтобы решить эту проблему, мне нужно отсортировать dict(), хотя dict() имеет огромное количество KEYS (максимум - 100000). Использование функции sorted() в моем коде не дает никакого эффекта. Есть ли быстрое решение? Спасибо за вашу помощь.

Мой код ниже:

for j in range(n): # n is the number of keys
        account = sys.stdin.readline().rstrip()
        dic.setdefault(account, 0)
        dic[account] += 1
sorted(dic) # **this sort take a lot of time**

---

EDIT1 : Согласно советам Джастина Пила, я обновляю код ниже, но возвращаю все еще TLE Как я могу это сделать?

import sys
import psyco # import psyco module to speed up
psyco.full()
nCase = int(sys.stdin.readline().split()[0])
for i in range(nCase):
    n = int(sys.stdin.readline().split()[0])
    dic = dict()
    lst = list()
    for j in range(n):
        account = sys.stdin.readline().rstrip()
        dic.setdefault(account, 0)
        dic[account] += 1
    sys.stdin.readline()
    lst = dic.keys() # store keys in list
    lst.sort()
    for account in lst:
        sys.stdout.write('%s %s\n' % (account, dic[account]))

Answer 1

dict s не отсортированы, поэтому они могут предоставить O (1) вставку и получить доступ.(Внутренне, они реализованы как хеш-таблицы, я думаю, хотя я не уверен, что это требуется спецификацией Python).

Если вы хотите перебрать ключи dict в отсортированном порядке,Вы можете использовать:

for key in sorted(the_dict.iterkeys()):
    value = the_dict[key]
    # do something

Но, как вы заметили, сортировка 100 000 элементов может занять некоторое время.

В качестве альтернативы вы можете написать (или найти в Интернете) отсортированные dict реализации, которые хранят упорядоченный список ключей вместе со словарем и поддерживают быстрый поиск по ключу и итерацию по порядку без необходимости сортировать все сразу.Конечно, чтобы поддерживать отсортированный порядок, ключи должны быть отсортированы во время вставки, поэтому вставки не будут иметь O (1).

Редактировать: За dsolimano * 1016Комментарий *, если вы используете Python 2.7 или Python 3.x, есть встроенный класс OrderedDict, который упорядочивает итерации в порядке вставки.Это обеспечивает быструю вставку, но может не выполнять то, что вам нужно (в зависимости от порядка элементов, которые вы хотите).

Answer 2

Мне удалось решить эту проблему. Вот несколько советов:

1. Используйте Python 2.5. Это намного быстрее, чем Python 3.2, который является другой опцией, доступной в SPOJ с Python. Только один человек смог получить достаточно быстрое решение, используя Python 3.2
2. Просто используйте базовый дикт для подсчета. Вы также можете обойтись с defaultdict из модуля коллекций, но основной диктат был для меня быстрее.
3. Сортировка только ключей из набора, а не пар ключ-элемент. Формирование пар ключ-элемент занимает слишком много времени. Кроме того, используйте keys = mydict.keys(); keys.sort(), потому что это самый быстрый способ сделать это.
4. Использовать psyco (почти всегда с проблемами SPOJ в Python)
5. Узнайте самые быстрые способы ввода и вывода в Python. Подсказка: он не повторяется, например, по каждой строке ввода.
6. Попробуйте отправить после добавления каждой части (получение данных, подсчет, выполнение вывода), чтобы узнать, где вы находитесь со временем. Это очень ценная вещь для SPOJ. Компьютер SPOJ, на котором выполняется ваш код, вероятно, работает намного медленнее, чем ваш текущий компьютер, и может быть сложно определить, будет ли он достаточно быстрым для SPOJ, основываясь на времени выполнения кода на вашем компьютере.

Answer 3

Поскольку Python 3.1 доступен, collections.Counter подходит для этой цели:

collections.Counter(map(str.rstrip, sys.stdin)).most_common()