Алгоритм сравнения списков: как его можно улучшить?

Question

Запуск на Python 3.3

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

Под «подобных элементов», я имею в виду два элемента, которые равны по значению (будь то string, int, что угодно).

В настоящее время я беру greedy approach по:

1. Сортировка списков, которые сравниваются,
2. Сравнивая каждый элемент в короткий список для каждого элемента в большем списке
3. Поскольку largeList и smallList, мы можем сохранить последний индекс, который был посещен,
4. Продолжить с предыдущего индекса (largeIndex).

В настоящее время, как правило, среднее время составляет O(nlog(n)). Об этом можно узнать по , который запускает тестовые примеры, перечисленные после этого блока кода.

Прямо сейчас, мой код выглядит так:

def compare(small,large,largeStart,largeEnd): 
     for i in range(largeStart, largeEnd): 
       if small==large[i]: 
        return [1,i] 
       if small<large[i]: 
        if i!=0: 
          return [0,i-1] 
        else: 
          return [0, i] 
     return [0,largeStart] 

    def determineLongerList(aList, bList): 
    if len(aList)>len(bList): 
     return (aList, bList) 
    elif len(aList)<len(bList): 
     return (bList, aList) 
    else: 
     return (aList, bList) 

    def compareElementsInLists(aList, bList): 
     import time 
     startTime = time.time() 
     holder  = determineLongerList(aList, bList) 
     sameItems = [] 
     iterations = 0 
     ########################################## 
     smallList = sorted(holder[1]) 
     smallLength = len(smallList) 
     smallIndex = 0 
     largeList = sorted(holder[0]) 
     largeLength = len(largeList) 
     largeIndex = 0 
     while (smallIndex<smallLength): 
       boolean = compare(smallList[smallIndex],largeList,largeIndex,largeLength) 
       if boolean[0]==1: 
        #`compare` returns 1 as True 
        sameItems.append(smallList[smallIndex]) 
        oldIndex = largeIndex 
        largeIndex = boolean[1] 
       else: 
        #else no match and possible new index 
        oldIndex = largeIndex 
        largeIndex = boolean[1] 
       smallIndex+=1 
       iterations =largeIndex-oldIndex+iterations+1 
     print('RAN {it} OUT OF {mathz} POSSIBLE'.format(it=iterations, mathz=smallLength*largeLength)) 
    print('RATIO:\t\t'+str(iterations/(smallLength*largeLength))+'\n') 
    return sameItems 

, а вот некоторые тестовые примеры:

def testLargest(): 
     import time 
     from random import randint 
     print('\n\n******************************************\n') 
     start_time = time.time() 
     lis = [] 
     for i in range(0,1000000): 
       ran = randint(0,1000000) 
       lis.append(ran) 
     lis2 = [] 
     for i in range(0,1000000): 
       ran = randint(0,1000000) 
       lis2.append(ran) 
     timeTaken = time.time()-start_time  
     print('CREATING LISTS TOOK:\t\t'+str(timeTaken)) 
     print('\n******************************************') 
     start_time = time.time() 
     c   = compareElementsInLists(lis, lis2) 
     timeTaken = time.time()-start_time  
     print('COMPARING LISTS TOOK:\t\t'+str(timeTaken)) 
     print('NUMBER OF SAME ITEMS:\t\t'+str(len(c))) 
     print('\n******************************************') 

    #testLargest() 

    ''' 
    One rendition of testLargest: 
     ****************************************** 

     CREATING LISTS TOOK:  21.009342908859253 

     ****************************************** 
     RAN 999998 OUT OF 1000000000000 POSSIBLE 
     RATIO:  9.99998e-07 

     COMPARING LISTS TOOK:  13.99990701675415 
     NUMBER OF SAME ITEMS:  632328 

     ****************************************** 
    ''' 

    def testLarge(): 
     import time 
     from random import randint 
     print('\n\n******************************************\n') 
     start_time = time.time() 
     lis = [] 
     for i in range(0,1000000): 
       ran = randint(0,100) 
       lis.append(ran) 
     lis2 = [] 
     for i in range(0,1000000): 
       ran = randint(0,100) 
       lis2.append(ran) 
     timeTaken = time.time()-start_time  
     print('CREATING LISTS TOOK:\t\t'+str(timeTaken)) 
     print('\n******************************************') 
     start_time = time.time() 
     c   = compareElementsInLists(lis, lis2) 
     timeTaken = time.time()-start_time  
     print('COMPARING LISTS TOOK:\t\t'+str(timeTaken)) 
     print('NUMBER OF SAME ITEMS:\t\t'+str(len(c))) 
     print('\n******************************************') 

    testLarge() 

Answer 1

Если вы просто ищете все элементы, которые находятся в обоих списках, вы должны использовать типы данных, предназначенные для решения таких задач. В этом случае должно быть уместно set s или bag. Они внутренне представлены механизмами хэширования, которые даже более эффективны, чем поиск в отсортированных списках.

(collections.Counter представляет собой подходящий bag.)

Если вы не заботитесь для сдвоенных элементов, то set s будет хорошо.

a = set(listA) 
print a.intersection(listB) 

Это напечатает все элементы, которые находятся в listA и в listB. (Без удвоенного выхода для сдвоенных входных элементов.)

import collections 

a = collections.Counter(listA) 
b = collections.Counter(listB) 

print a & b 

Это будет печатать, сколько элементов, как часто в обоих списках.

Я не делал никаких измерений, но я уверен, что эти решения быстрее, чем ваши собственные попытки.

Чтобы преобразовать счетчик в list всех представленных здесь элементов, вы можете использовать list(c.elements()).

Answer 2

Использование IPython магии для timeit, но это не выгодно просто стандарт set() пересечение.
установки:

import random 
alist = [random.randint(0, 100000) for _ in range(1000)] 
blist = [random.randint(0, 100000) for _ in range(1000)] 

Сравнить элементы:

%%timeit -n 1000 
compareElementsInLists(alist, blist) 
1000 loops, best of 3: 1.9 ms per loop 

Vs Set перекрестков

%%timeit -n 1000 
set(alist) & set(blist) 
1000 loops, best of 3: 104 µs per loop 

Просто, чтобы убедиться, что мы получим те же результаты:

>>> compareElementsInLists(alist, blist) 
[8282, 29521, 43042, 47193, 48582, 74173, 96216, 98791] 
>>> set(alist) & set(blist) 
{8282, 29521, 43042, 47193, 48582, 74173, 96216, 98791}