Каков наилучший способ сортировки хеш-таблицы по значению? - PullRequest
Новая
       15

Каков наилучший способ сортировки хеш-таблицы по значению?

6 голосов
/ 22 сентября 2011

Теперь мне нужно скопировать hastable в список перед сортировкой: 

(defun good-red ()
  (let ((tab (make-hash-table)) (res '()))
    (dotimes (i 33) (setf (gethash (+ i 1) tab) 0))
    (with-open-file (stream "test.txt")
        (loop for line = (read-line stream nil)
             until (null line)
             do
                (setq nums (butlast (str2lst (substring line 6))))
                (dolist (n nums) (incf (gethash n tab)))
                ))
    **(maphash #'(lambda (k v) (push (cons k v) res)) tab)**
    (setq sort-res (sort res #'< :key #'cdr))
    (reverse (nthcdr (- 33 18) (mapcar #'car sort-res))) ))

Кстати, как лучше выбрать первые N элементов списка?

Ответы [ 2 ]

12 голосов
/ 06 июня 2012

Ответ Ватина технически верен, но, вероятно, не очень полезен для непосредственной проблемы, когда кто-то задает этот вопрос. Распространенный случай использования хеш-таблицы для хранения коллекции счетчиков, а затем выбора первых N элементов по счету может быть выполнен следующим образом: 

;; convert the hash table into an association list
(defun hash-table-alist (table)
  "Returns an association list containing the keys and values of hash table TABLE."
  (let ((alist nil))
    (maphash (lambda (k v)
               (push (cons k v) alist))
             table)
    alist))

(defun hash-table-top-n-values (table n)
  "Returns the top N entries from hash table TABLE. Values are expected to be numeric."
  (subseq (sort (hash-table-alist table) #'> :key #'cdr) 0 n))

Первая функция возвращает содержимое хеш-таблицы в виде серии пар cons в списке, который называется списком ассоциаций (типичное представление списка для пар ключ / значение). Большинство энтузиастов Лиспа уже имеют вариант этой функции под рукой, потому что это такая обычная операция. Эта версия взята из библиотеки Александрия , которая очень широко используется в сообществе CL.

Вторая функция использует SUBSEQ для извлечения первых N элементов из списка, возвращенного путем сортировки списка, возвращенного первой функцией, используя CDR каждой пары в качестве ключа. Изменение: ключ к # 'машина сортирует по хеш-ключам, изменение #'> на # '<инвертирует порядок сортировки. </p>

3 голосов
/ 22 сентября 2011

Хеш-таблица по своей природе неупорядочена. Если вы хотите, чтобы это было отсортировано, вам нужно инициализировать некоторую упорядоченную структуру данных с содержимым.

Если вы хотите получить первые N элементов последовательности, всегда есть SUBSEQ.

...