Как быстро сортировать 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

Я был в состоянии решить эту проблему. Вот несколько советов:

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

Answer 2

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

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

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

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

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

Edit: комментарий Per dsolimano «s, если вы используете Python 2.7 или Python 3.x, есть встроенный OrderedDict класса, что заказы итерация в порядке ввода. Это позволяет быстро вставать, но может не делать то, что вам нужно (в зависимости от того, какой заказ вы хотите).

Answer 3

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

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