как реализовать действительно эффективную сортировку битвекторов в python - PullRequest
Новая
       16

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

4 голосов
/ 07 июня 2010

На самом деле это интересная тема из программирования жемчужин, сортировки 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
  • функция сортировки занимает 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

  • Функция сортировки занимает 12,9204008579
  • Функция vec_sort занимает 38.8053860664

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

Ответы [ 2 ]

3 голосов
/ 07 июня 2010

Как указал Ники, вы сравниваете очень быструю процедуру 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. Прежде чем я нашел bitarray, я сделал несколько различных настроек модуля и, используя мой модуль, который имеет настройки, время для vec_sort сокращается за секунду для этого размера массива. Я не отправил свои изменения, потому что bitarray намного быстрее.

1 голос
/ 07 июня 2010

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

bv = BitVector( size = len(input_li) )

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

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

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

...