VPF::как максимально быстро сравнить два списка

Artemios

Дата 9.12.2006, 06:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

Поигрался немного с кодом. psyco неимею, поэтому убрал.

Код


# -*- coding: utf8 -*-
import time, random
from sets import Set

def check_similarity (check_function, spisok, message):
    print '\n', message
    spisok_size = len(spisok)
    t = time.time()
    for i in xrange(spisok_size):
        for j in xrange(i+1, spisok_size):
            check_function(spisok[i], spisok[j])
    print time.time() - t, ' seconds'

def list_similarity1 (list1, list2):
    s1 = Set(list1)
    s2 = Set(list2)
    return list(s1 & s2)

#def list_similarity2 (list1, list2):
    #return [i for i in list1 if i in list2]

def list_similarity3 (list1, list2):
    s2 = dict.fromkeys(list2)
    return [s for s in list1 if s in s2]

def list_similarity4 (list1, list2):
    if len(list1)<=len(list2):
        s2 = dict.fromkeys(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = dict.fromkeys(list1)
        return [s for s in list2 if s in s1]
    
def list_similarity5 (list1, list2): 
    s1 = Set(list1) 
    return [i for i in list2 if i in s1]

def list_similarity12 (list1, list2):
    s1 = set(list1)
    s2 = set(list2)
    return list(s1 & s2)

def list_similarity42 (list1, list2):
    if len(list1)<=len(list2):
        s2 = set(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = set(list1)
        return [s for s in list2 if s in s1]

def list_similarity52 (list1, list2): 
    s1 = set(list1) 
    return [i for i in list2 if i in s1]

print 'generation test set'
spisok = []
spisok_size = 100
all_values = [random.randint(0, 1000000) for i in range(1000000)]
for i in range(spisok_size):
    spisok.append(random.sample(all_values, 1000))

print 'testing'
print (spisok_size * spisok_size + spisok_size)/2, ' operations'
check_similarity(list_similarity1, spisok, '1')
#check_similarity(list_similarity2, spisok, '2')
check_similarity(list_similarity3, spisok, '3')
check_similarity(list_similarity4, spisok, '4')
check_similarity(list_similarity5, spisok, '5')
check_similarity(list_similarity12, spisok, '1_2')
check_similarity(list_similarity42, spisok, '4_2')
check_similarity(list_similarity52, spisok, '5_2')

На своей машине получил:

Цитата

1
7.00922703743  seconds

3
3.62788891792  seconds

4
3.61328196526  seconds

5
9.78012800217  seconds

1_2
4.05814909935  seconds

4_2
3.58052396774  seconds

5_2
3.28020095825  seconds

(1,3,4,5 остались старые, номер 2 выдавал 400 с чем-то секунд, но меня ломало каждый раз его ждать и тоже убрал; 1_2, 4_2, 5_2 -- заменил структуры в нужных местах соответствующих функций на стандартное множество -- set)
Вывод: set предпочтителен.

Далее, самую быструю 5_2 "в лоб" переписал на pyrex (входной язык -- немного "исковерканный" Питон, предназначена для простого (и неоптимального smile

) написания модулей расширения под Питон); а также туда же забил check_similarity, только сузив ее применение: функций сравнения аргументом не принимает, внутри в цикле организована все та же 5_2. В конечном итоге на pyrex имел следующий код:

Код


import time

def list_similarity52(list1, list2): 
    s1 = set(list1)
    res = []
    for i in list2:
        if i in s1:
            res.append(i)
    return res

def check_similarity53(spisok, message):
    print '\n', message
    cdef int spisok_size,i,j
    spisok_size = len(spisok)
    t = time.time()
    for i from 0 <=i < spisok_size:
        for j from i+1 <=j < spisok_size:
            s1 = set(spisok[1])
            res = []
            for i in spisok[2]:
                if i in s1:
                    res.append(i)
    print time.time() - t, ' seconds'

после его трансляции в Си и компиляции в модуль check_pyrex.so -- могу использовать в Питоне, и завершающий код:

Код


# -*- coding: utf8 -*-
import time, random

from sets import Set

import check_pyrex

def check_similarity (check_function, spisok, message):
    print '\n', message
    spisok_size = len(spisok)
    t = time.time()
    for i in xrange(spisok_size):
        for j in xrange(i+1, spisok_size):
            check_function(spisok[i], spisok[j])
    print time.time() - t, ' seconds'

def list_similarity1 (list1, list2):
    s1 = Set(list1)
    s2 = Set(list2)
    return list(s1 & s2)

#def list_similarity2 (list1, list2):
    #return [i for i in list1 if i in list2]

def list_similarity3 (list1, list2):
    s2 = dict.fromkeys(list2)
    return [s for s in list1 if s in s2]

def list_similarity4 (list1, list2):
    if len(list1)<=len(list2):
        s2 = dict.fromkeys(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = dict.fromkeys(list1)
        return [s for s in list2 if s in s1]
    
def list_similarity5 (list1, list2): 
    s1 = Set(list1) 
    return [i for i in list2 if i in s1]

def list_similarity12 (list1, list2):
    s1 = set(list1)
    s2 = set(list2)
    return list(s1 & s2)

def list_similarity42 (list1, list2):
    if len(list1)<=len(list2):
        s2 = set(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = set(list1)
        return [s for s in list2 if s in s1]

def list_similarity52 (list1, list2): 
    s1 = set(list1) 
    return [i for i in list2 if i in s1]

print 'generation test set'
spisok = []
spisok_size = 100
all_values = [random.randint(0, 1000000) for i in range(1000000)]
for i in range(spisok_size):
    spisok.append(random.sample(all_values, 1000))

print 'testing'
print (spisok_size * spisok_size + spisok_size)/2, ' operations'
check_similarity(list_similarity1, spisok, '1')
#check_similarity(list_similarity2, spisok, '2')
check_similarity(list_similarity3, spisok, '3')
check_similarity(list_similarity4, spisok, '4')
check_similarity(list_similarity5, spisok, '5')
check_similarity(list_similarity12, spisok, '1_2')
check_similarity(list_similarity42, spisok, '4_2')
check_similarity(list_similarity52, spisok, '5_2')
check_similarity(check_pyrex.list_similarity52, spisok, '5_2_pyrex')
check_pyrex.check_similarity53(spisok, '5_3_pyrex')

на моей машине дал следующий результат:

Цитата

1
7.0034198761  seconds

3
3.61762213707  seconds

4
3.60377693176  seconds

5
9.67175197601  seconds

1_2
4.02275705338  seconds

4_2
3.56534600258  seconds

5_2
3.29011011124  seconds

5_2_pyrex
2.38613009453  seconds

5_3_pyrex
0.0568170547485  seconds

Вывод: отдельную функцию сравнения переписывать на Си -- не принесет ощутимого выигрыша.

Это сообщение отредактировал(а) Artemios - 9.12.2006, 06:46

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 9.12.2006, 14:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

Извиняюсь, вариант 5_3_pyrex неверен, ошибся в коде check_similarity53.
Правильный вариант модуля на pyrex:

Код


import time

def list_similarity52(list1, list2): 
    s1 = set(list1)
    res = []
    for i in list2:
        if i in s1:
            res.append(i)
    return res

def check_similarity53(spisok, message):
    print '\n', message
    cdef int spisok_size,i,j
    spisok_size = len(spisok)
    t = time.time()
    for i from 0 <=i < spisok_size:
        s1 = set(spisok[i])
        for j from i+1 <=j < spisok_size:
            res = []
            for x in spisok[j]:
                if x in s1:
                    res.append(x)
    print time.time() - t, ' seconds'

дальше, Питон без изменения и тест:

Цитата

1
7.58109593391  seconds

3
3.63567996025  seconds

4
3.61104297638  seconds

5
9.99201393127  seconds

1_2
4.05328583717  seconds

4_2
3.55678391457  seconds

5_2
3.25729894638  seconds

5_2_pyrex
2.39998984337  seconds

5_3_pyrex
1.1331179142  seconds

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 9.12.2006, 15:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

А вот такой результат получил на той же машине:

Цитата

6
1.10187888145 seconds

сформировав в spisok не список списков, а список множеств, и применяя к нему упрощенный вариант 1_2:

Код


# -*- coding: utf8 -*-
import time, random

def check_similarity (check_function, spisok, message):
    print '\n', message
    spisok_size = len(spisok)
    t = time.time()
    for i in xrange(spisok_size):
        for j in xrange(i+1, spisok_size):
            check_function(spisok[i], spisok[j])
    print time.time() - t, ' seconds'

def list_similarity6 (set1, set2):
    return set1 & set2

print 'generation test set'
spisok = []
spisok_size = 100
all_values = [random.randint(0, 1000000) for i in range(1000000)]
for i in range(spisok_size):
    spisok.append(set(random.sample(all_values, 1000)))

print 'testing'

check_similarity(list_similarity6, spisok, '6')

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

kulibinka

Дата 9.12.2006, 15:11 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4

За неимением понимания pyrex поигрался с вашими ф-ями (засунул их в psyco)

Код


# -*- coding: windows-1251 -*-
#    сравниваю еффективность разных ф-й для подсчета схожести всех елементов 2-х списков

import time, random, psyco
from sets import Set

def check_similarity (check_function, spisok, message):
    """получаем ф-ю и список, возвращаем время проверки"""
    print '\n', message
    spisok_size = len(spisok)
    t = time.time()
    for i in range(spisok_size):
        for j in range(i+1, spisok_size):
            check_function(spisok[i], spisok[j])
    print time.time() - t, ' seconds'

def list_similarity1 (list1, list2):
    s1 = Set(list1)
    s2 = Set(list2)
    return list(s1 & s2)

def list_similarity2 (list1, list2):
    return [i for i in list1 if i in list2]

def list_similarity3 (list1, list2):
    s2 = dict.fromkeys(list2)
    return [s for s in list1 if s in s2]

def list_similarity4 (list1, list2):
    if len(list1)<=len(list2):
        s2 = dict.fromkeys(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = dict.fromkeys(list1)
        return [s for s in list2 if s in s1]

def list_similarity5 (list1, list2): 
    s1 = Set(list1) 
    return [i for i in list1 if i in s1]


def list_similarity12 (list1, list2):
    s1 = set(list1)
    s2 = set(list2)
    return list(s1 & s2)

def list_similarity42 (list1, list2):
    if len(list1)<=len(list2):
        s2 = set(list2)
        return [s for s in list1 if s in s2]
    else:
        s1 = set(list1)
        return [s for s in list2 if s in s1]

def list_similarity52 (list1, list2): 
    s1 = set(list1) 
    return [i for i in list2 if i in s1]



list_similarity11 = psyco.proxy(list_similarity1)
list_similarity21 = psyco.proxy(list_similarity2)
list_similarity31 = psyco.proxy(list_similarity3)
list_similarity41 = psyco.proxy(list_similarity4)
list_similarity51 = psyco.proxy(list_similarity5)
list_similarity121 = psyco.proxy(list_similarity12)
list_similarity421 = psyco.proxy(list_similarity42)
list_similarity521 = psyco.proxy(list_similarity52)

#генерация списков
print 'generation test set'
spisok = []
spisok_size = 100
all_values = [random.randint(0, 1000000) for i in range(1000000)]
for i in range(spisok_size):
    spisok.append(random.sample(all_values, 1000))

#тестирую ф-ии
print 'testing'
print (spisok_size * spisok_size + spisok_size)/2, ' operations'
check_similarity(list_similarity1, spisok, '1')
#check_similarity(list_similarity2, spisok, '2')
check_similarity(list_similarity3, spisok, '3')
check_similarity(list_similarity4, spisok, '4')
check_similarity(list_similarity5, spisok, '5')
check_similarity(list_similarity12, spisok, '12')
check_similarity(list_similarity42, spisok, '42')
check_similarity(list_similarity52, spisok, '52')

check_similarity(list_similarity11, spisok, '11')
#check_similarity(list_similarity21, spisok, '21')
check_similarity(list_similarity31, spisok, '31')
check_similarity(list_similarity41, spisok, '41')
check_similarity(list_similarity51, spisok, '51')

check_similarity(list_similarity121, spisok, '121')
check_similarity(list_similarity421, spisok, '421')
check_similarity(list_similarity521, spisok, '521')

Вот результаты:

Цитата

1
20.3900001049  seconds

3
10.3249998093  seconds

4
10.1940000057  seconds

5
37.5740001202  seconds

12
11.0559999943  seconds

42
9.93400001526  seconds

52
9.6139998436  seconds

11
15.3519999981  seconds

31
7.5110001564  seconds

41
7.50099992752  seconds

51
32.1660001278  seconds

121
11.1459999084  seconds

421
7.23099994659  seconds

521
5.50699996948  seconds

Как видно, ф-я 521 (52 с использованием psyco) работает почти в 4 раза быстрее чем моя начальная - еще лучше smile

А не скажете насколько скорость результатов на pyrex приближается к скорости на чистом Си?

Если они идентичны, то 52 с использованием psyco (у меня ф-я 1 - 20.3900001049 , эта 5.50699996948 - в 3.6 раз выше скорость) лучше чем 52 на Си (у вас ф-я 1 - 7.58109593391, а 52 на pyrex 2.39998984337 - в 3.1 раз выше скорость).

А значит использование psyco дает максимальную производительность.

kulibinka

Дата 9.12.2006, 15:58 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4

Цитата

А вот такой результат получил на той же машине сформировав в spisok не список списков, а список множеств, и применяя к нему упрощенный вариант 1_2

Гениально.
Вот то за что я так долго боролся - Artemios, ОГРОМНОЕ СПАСИБО smile

И даже psyco только ухудшает результаты smile

И я сомневаюсь что есть какой-либо другой ощутимо более производительный способ решения этой задачи.

Это сообщение отредактировал(а) kulibinka - 9.12.2006, 16:21

Artemios

Дата 10.12.2006, 04:22 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

Цитата(kulibinka @ 9.12.2006, 15:58

)

И даже psyco только ухудшает результаты

psyco, как я понимаю, оптимизирует байт-код Питона, а в No 6 его почти небудет -- builtin функции, реализованные, как и весь Питон, на Си.

Кстати, по поводу реализации. Все предыдущие тесты я проводил в ОС Linux на Python 2.4.
Попробовал в Windows-е для ф-й 1,3,4,5,12,42,52 и отдельно для 6:
на Python 2.4 результаты примерно такие же;
на Python 2.5 примерно на пол-секунды лучше прежнего работают варианты 12,42,52 (10%-15% относительного времени),
а вот 6-й:

Цитата

6
0.40700006485 seconds

против 1-й секунды Питона 2.4, так что разработчики не обманывали, когда говорили, что 5-я версия работает быстрее.

Цитата(kulibinka @ 9.12.2006, 15:58

)

И я сомневаюсь что есть какой-либо другой ощутимо более производительный способ решения этой задачи.

Оптимизировать в принципе возможно, переписав всю задачу на Си. Как видим, разработчики Питона доказывают, что при грамотном программировании на низкоуровневом языке производительность можно существенно увеличить smile

Цитата(kulibinka @ 9.12.2006, 15:11

)

А не скажете насколько скорость результатов на pyrex приближается к скорости на чистом Си?

Если один-в-один перебивать питоновский код в pyrex -- производительность модуля на pyrex особо не возрастет (каждая строчка в стиле python-а будет транслирована в гору сишного кода). Лично мне pyrex понравился, как простенький переходничок для подключения си-шных библиотек, так как в нем можно комбинировать использование и питоновских объектов, и сишных типов, и преобразования между ними.

Это сообщение отредактировал(а) Artemios - 10.12.2006, 04:24

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

kulibinka

Дата 10.12.2006, 18:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4

Цитата

6
0.40700006485 seconds

против 1-й секунды Питона 2.4, так что разработчики не обманывали, когда говорили, что 5-я версия работает быстрее.

Обрадованный возможностью настолько сильно повысить производительность не поленился поставить 5-й питон.
На моих реальных данных (проверял на шингловость множество из 6000 случайных статей) его скорость равна один в один с 4-й.

Возможно в 5-й сделали пооптимальнее сравнение множеств одинаковых размеров. Поэтому в нашем тестовом варианте производительность повысилась, а в моей проверке на шинглах осталась такой же.

Artemios

Дата 10.12.2006, 20:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

жаль. А на реальных данных в сравниваемых множествах элементы какого типа (т.е., для которых у нас тестовый аналог случайные целые числа)?
Прото работа с множеством set тем эффективнее, чем эффективнее заданы методы __hash__() для элементов множества. Пример:

Код


>>> a = 5
>>> a.__hash__()
5
>>> b = '5'
>>> b.__hash__()
6784020404
>>> c = ord(b)
>>> c
53
>>> c.__hash__()
53

Поэтому, если допустим в множестве храним отдельные символы, то возможным шагом оптимизации будет предварительное преобразование символьных объектов в числовые (например функцией ord).

kulibinka, а нельзя ли здесь выложить (приаттачить к сообщению) код основной программы и несколько статей для теста?

Это сообщение отредактировал(а) Artemios - 10.12.2006, 20:50

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

Artemios

Дата 10.12.2006, 23:19 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 405
Регистрация: 14.8.2006
Где: Саратов, Россия

Репутация: 18
Всего: 50

P.S. Я тут подумал... Если атомарные объекты -- не отдельные символы, а целые строки (слова), и при дальнейшем использовании не требуется конкретного содержания строки, а важна лишь возможность их сравнивать между собой, то имеет смысл заменить слова их хэшами, и сравнивать за тем полученные целые числа (для равных строк хэши равны, для разных -- вероятность совпадения хэшей почти нулевая)

--------------------

fib = 1: 1: [ x+y | (x,y) <- zip fib (tail fib) ]

kulibinka

Дата 11.12.2006, 01:03 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 191
Регистрация: 20.11.2006

Репутация: 2
Всего: 4

Насчет кода и статей написал Вам в личку.

А насчет создания хешей то у меня так все и реализовано (см. код).

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Python: Общие вопросы \| Следующая тема »