как реализовать действительно эффективную сортировку битовых векторов в python

На самом деле это интересная тема из жемчуга программирования, сортировка 10-значных телефонных номеров в ограниченной памяти с эффективным алгоритмом. Вы можете найти всю историю здесь

Что меня интересует, так это то, насколько быстрой может быть реализация на python. Я сделал наивную реализацию с модулем bitvector. Код выглядит следующим образом:

from BitVector import BitVector
import timeit
import random
import time
import sys

def sort(input_li):
        return sorted(input_li)

def vec_sort(input_li):
        bv = BitVector( size = len(input_li) )
        for i in input_li:
                bv[i] = 1

        res_li = []
        for i in range(len(bv)):
                if bv[i]:
                        res_li.append(i)

        return res_li

if __name__ == "__main__":
        test_data = range(int(sys.argv[1]))
        print 'test_data size is:', sys.argv[1]
        random.shuffle(test_data)

        start = time.time()
        sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "vec_sort function takes " + str(elapsed)

Я протестировал размер массива от 100 до 10 000 000 в своем macbook (2 ГГц Intel Core 2 Duo 2 ГБ SDRAM), результат следующий:

  • размер test_data: 1000
  • функция sort принимает 0,000274896621704

  • Функция vec_sort принимает значение 0,00383687019348.

  • размер test_data: 10000

  • функция сортировки занимает 0,00380706787109

  • функция vec_sort принимает 0,0371489524841

  • размер test_data: 100000

  • функция сортировки занимает 0,0520560741425

  • функция vec_sort занимает 0,374383926392

  • размер test_data: 1000000

  • функция сортировки принимает 0,867373943329

  • функция vec_sort занимает 3,80475401878

  • размер test_data: 10000000

  • функция sort принимает 12.9204008579
  • Функция vec_sort занимает 38,8053860664

Что меня разочаровывает, так это то, что даже когда размер test_data равен 100 000 000, функция сортировки все равно работает быстрее, чем vec_sort. Есть ли способ ускорить функцию vec_sort?


python sorting algorithm bitvector
person xiao 啸    schedule 07.06.2010    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Как заметил Ники, вы сравниваете очень быструю процедуру C с процедурой Python. Использование psyco немного ускоряет его для меня, но вы действительно можете ускорить его, используя битовый вектор модуль, написанный на C. Я использовал bitarray, и тогда метод сортировки по битам превосходит встроенная сортировка для массива размером около 250 000 с использованием psyco.

Вот функция, которую я использовал:

def vec_sort2(input_li):
    bv = bitarray(len(input_li))
    bv.setall(0)
    for i in input_li:
        bv[i] = 1

    return [i for i in xrange(len(bv)) if bv[i]]

Обратите также внимание, что я использовал понимание списка для создания отсортированного списка, что немного помогает. Используя psyco и вышеуказанную функцию с вашими функциями, я получаю следующие результаты:

test_data size is: 1000000
sort function takes 1.29699993134
vec_sort function takes 3.5150001049
vec_sort2 function takes 0.953999996185

Кстати, BitVector не оптимизирован даже для Python. Прежде чем я нашел битовый массив, я сделал несколько различных настроек модуля, и с помощью моего модуля, который имеет настройки, время для vec_sort сократилось более чем на секунду для такого размера массива. Я не отправлял в него свои изменения, потому что битовый массив намного быстрее.

person Justin Peel    schedule 07.06.2010

arrow_upward
1
arrow_downward

Мой Python не самый лучший, но похоже, что у вас есть ошибка в коде:

bv = BitVector( size = len(input_li) )

Размер вашего битового вектора совпадает с размером вашего входного массива. Вы хотите, чтобы битовый вектор был размером с ваш домен — 10^10. Я не уверен, как битовые векторы Python справляются с переполнением, но если он автоматически изменяет размер битового вектора, вы получаете квадратичное поведение.

Кроме того, я предполагаю, что функция сортировки Python реализована на C и не будет иметь накладных расходов, связанных с сортировкой, реализованной исключительно на Python. Однако это, вероятно, не приведет к тому, что алгоритм O (nlogn) будет работать значительно быстрее, чем алгоритм O (n).

Изменить: также этот вид будет работать только с большими наборами данных. Ваш алгоритм работает за время O (n + 10 ^ 10) (основываясь на ваших тестах, я полагаю, вы это знаете), что будет хуже, чем O (nlogn) для небольших входных данных.

person Niki Yoshiuchi    schedule 07.06.2010