LINUX.ORG.RU
Форум — Development  

Оптимизация поиска _наличия_ общего элемента 2х списков

 , .net,


0

3

интересно как можно оптимизировать по времени, наверняка с лёту накидаете кучу крутых вариантов с параллельными последовательностями и прочими заумными вещами) Вот пара простых вариантов: 

type Comparer<'a>(f) =
    interface System.Collections.Generic.IEqualityComparer<'a> with
        member x.Equals(a, b) =
            f a b
        member x.GetHashCode(a) = hash(a.ToString())

let haveIntersection eq (l1 : 'a list) l2 =
    l1 |> List.exists (fun a -> l2 |> List.exists (fun b -> eq a b))

let _haveIntersection eq (l1 : 'a list) l2 =
    l1.Intersect(l2, Comparer<'a>(eq)).Any()

let l1 = [1L .. 10000L]
let l2 = [1L .. 10000L]

let eq a b = a = b && a = 10000L

> _haveIntersection eq l1 l2;;
Real: 00:00:00.007, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = true
> haveIntersection eq l1 l2;;
Real: 00:00:06.355, CPU: 00:00:06.328, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = true

★★★

Последнее исправление: pseudo-cat (всего исправлений: 1)
← Совет по архитектуре
Как узнать, под какими дефайнами находится код? →

List.exists

Слить один List в Set, а по второму сделать List.TryFind (fun elem -> s.Contains elem).

Set должен быть более эффективен в поиске элементов, а TryFind будет искать до первого пересечения.

Norgat ★★★★★
()
Ответ на: комментарий от Norgat 
let __haveIntersection eq (l1 : 'a list) l2 =
    let set = Microsoft.FSharp.Collections.Set.ofList(l1)
    l2 
    |> List.exists 
        (fun a -> set.Contains(a, Comparer(eq)))

> __haveIntersection eq l1 l2;;
Real: 00:00:15.962, CPU: 00:00:15.796, GC gen0: 3053, gen1: 2, gen2: 0
val it : bool = true

абсолютный рекордсмен :)

pseudo-cat ★★★
() автор топика
Ответ на: комментарий от pseudo-cat

я ваши фшарпы не знаю, но логично мерять максимальное время на поиск, т.е. когда списки почти наверняка разные, а совпадает к примеру последний элемент (и то для теста):

~$ cat 1.cpp
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <unordered_set>
#include <vector>
using namespace std;

int main() {
	srand( time( 0 ) );
	unordered_set<int> us;

  	vector<int> v1( 10000 ), v2( 10000 );
	generate( v1.begin(), v1.end(), rand );
	generate( v2.begin(), v2.end(), rand );

	v1.push_back( 9999 );
	v2.push_back( 9999 );

	for( int n : v1 )
		us.emplace( n );

	for( int n : v2 ) {
		if( us.find( n ) != us.end() ) {
			printf( "Yes: %d\n", n );
			return 0;
		}
	}

	printf( "No\n" );
}

~$ g++ -Ofast -std=c++11 1.cpp
~$ time ./a.out 
Yes: 9999

real	0m0.005s
user	0m0.004s
sys	0m0.004s

и если время выше таки в секундах - то ваш fsharp нереально тормозной

wota ★★
()
Последнее исправление: wota (всего исправлений: 1)

l1.Intersect

А где этот метод то есть? Что-то я его не вижу ни в VS, ни в документации.

Norgat ★★★★★
()

А так, самое быстрое, что у меня получилось:

let r = Random()

let l1 = [for i in 1 .. 10000 -> r.Next()]
let l2 = [for i in 1 .. 10000 -> r.Next()]

let eq a b = a = b

let hIn eq l1 l2 =
    None <> List.tryFind (fun e1 -> None <> List.tryFind (fun e2 -> eq e1 e2) l2) l1

Вызов такой:

> hIn eq l1 (List.filter (fun e -> e = 10000) l2);;
Real: 00:00:00.003, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn eq l1 (List.filter (fun e -> e > 2000) l2);;
Real: 00:00:04.260, CPU: 00:00:04.265, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn eq l1 (List.filter (fun e -> e > 1000) l2);;
Real: 00:00:04.426, CPU: 00:00:04.421, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn eq l1 (List.filter (fun e -> e > 1106) l2);;
Real: 00:00:04.367, CPU: 00:00:04.375, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn eq l1 (List.filter (fun e -> e > 5 && e < 100) l2);;
Real: 00:00:00.001, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

Заметь, что условие из eq (a = 10000) проверяется до поиска. Если это условие снижает размер одного из списков, то это значительно ускоряет проверку (см. 1 и последний запуск).

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

Вот так будет быстрее:

open System
open System.Collections.Generic

type Comparer<'a>(f) =
    interface System.Collections.Generic.IEqualityComparer<'a> with
        member x.Equals(a, b) =
            f a b
        member x.GetHashCode(a) = hash(a.ToString())

let r = Random()

let l1 = [for i in 1 .. 10000 -> r.Next()]
let l2 = [for i in 1 .. 10000 -> r.Next()]

let eq a b = a = b && a = 10000

let hIn2 eq (l1: 'a list) l2 = 
    let s = System.Collections.Generic.HashSet<'a>(l1, Comparer<'a>(eq))
    None <> List.tryFind (fun e -> s.Contains e) l2


> hIn2 eq l1 l2;;
Real: 00:00:00.005, CPU: 00:00:00.000, GC gen0: 1, gen1: 0, gen2: 0
Norgat ★★★★★
()
Ответ на: комментарий от wota

c rand не логично мерить, 

 
let l1 = [1 .. 1000000] // два списка одинаковой длины
let l2 = [1 .. 1000000]

let eq a b = a = b && a = 1000000L // поиск удастся, если при последовательном переборе будут рассмотрены последние элементы каждого из списка 



сделай такие входные данные, тогда можно сравнить ради интереса.
pseudo-cat ★★★
() автор топика
Ответ на: комментарий от Norgat

вот только почему 

let l = [1L .. 10000000L]
let eq a b = a = b
let s = System.Collections.Generic.HashSet<'a>(l, Comparer<'a>(eq))


> l |> List.exists (fun a -> a = 0L);;
Real: 00:00:00.060, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> l |> List.exists (fun a -> a = 0L);;
Real: 00:00:00.060, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> l.Contains 0L;;
Real: 00:00:00.266, CPU: 00:00:00.265, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> l.Contains 0L;;
Real: 00:00:00.251, CPU: 00:00:00.250, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
>

pseudo-cat ★★★
() автор топика
Последнее исправление: pseudo-cat (всего исправлений: 3)
Ответ на: комментарий от pseudo-cat 
~$ cat ./1.cpp
#include <cstdio>
#include <cstdlib>
#include <unordered_set>
using namespace std;

struct eq {
	bool operator()(int x,int y) const { return x == y && y == 1000000; }
};

int main() {
  	int v1[ 1000000 ], v2[ 1000000 ];
	for( int i = 0 ; i < 1000000 ; ++i ) {
		v1[ i ] = v2[ i ] = i + 1;
	}

	clock_t start = clock();

	unordered_set<int,hash<int>,eq> us;
	for( int n : v1 )
		us.emplace( n );

	for( int n : v2 ) {
		if( us.find( n ) != us.end() ) {
			printf( "Found - %d\n", n );
			break;
		}
	}

	printf( "%.3fsec\n", ( clock() - start ) * 1.f / CLOCKS_PER_SEC );
}

~$ g++ -Ofast -std=c++11 1.cpp
~$ ./a.out 
Found - 1000000
0.060sec
wota ★★
()
Ответ на: комментарий от pseudo-cat 
> l.Contains 0L;;
Real: 00:00:00.251, CPU: 00:00:00.250, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

Код полностью приведи. Ибо у меня:

> l |> List.exists (fun a -> a = 1000000000L);;
Real: 00:00:00.050, CPU: 00:00:00.046, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

> s.Contains 1000000000L;;
Real: 00:00:00.000, CPU: 00:00:00.000, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
Norgat ★★★★★
()

1. Отсортировать списки O(nlogn)
2. Поиск общего элемента O(n)
Итого: O(n+nlogn), никаких O(n^2) как тут советуют

d_Artagnan ★★
()

Задача похожа на JOIN в СУБД. Так что стоит покурить, как в СУБД оптимизируется JOIN.

kvap ★
()
Ответ на: комментарий от d_Artagnan

В принципе, на хештаблицах алгоритм достигает O(n) как у товарища wota

Вот только эту задачу нельзя решить быстрее O(nlog n). Доказанный результат и все такое.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Вот только эту задачу нельзя решить быстрее O(nlog n)

если значения имеют, к примеру, тип int16_t, то банальный битсет размером в 8Кб даст O(n)

wota ★★
()
Ответ на: комментарий от wota

если значения имеют, к примеру, тип int16_t, то банальный битсет размером в 8Кб даст O(n)

если =)

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

O(nlog n)

Откуда вы все взяли log(n)? Логарифмеческая сложность поиска возникает при использовании деревьев, а это SortedSet и IComparable в .Net.

При использовании HashSet сложность поиска, вставки и удаления элемента, в среднем, O(1). Поэтому итоговая сложность задачи, при использовании HashSet, O(n + m) - средняя оценка сверху (заполнение HashSet + проход по второму списку и поиск элементов в HashSet).

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

При использовании HashSet сложность поиска, вставки и удаления элемента, в среднем, O(1)

в самом лучшем случае, а в самом худшем O(n)

wota ★★
()
Ответ на: комментарий от kvap

Так что стоит покурить, как в СУБД оптимизируется JOIN.

индексами, в том числе временными

wota ★★
()
Ответ на: комментарий от wota

в самом лучшем случае, а в самом худшем O(n)

Не так. Мат. ожидание, в общем случае, стремиться к O(1), поэтому вероятность худшего случая исчезающе мала. В исходном посте используются числа, так что оч. сомнительно, что они могут вызвать худший случай поиска.

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

Откуда вы все взяли log(n)? Логарифмеческая сложность поиска возникает при использовании деревьев, а это SortedSet и IComparable в .Net.

Оттуда. Читай классиков.

При использовании HashSet сложность поиска, вставки и удаления элемента, в среднем, O(1).

Такой структуры данных, как ты описал, не существует.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Такой структуры данных, как ты описал, не существует.

http://ru.wikipedia.org/wiki/Хеш-таблица

А теперь уточним, что увеличение сложности доступа от O(1) к O(n) возникает в зависимости от количества коллизий(что определяется качеством хеш-функции, а хеши для строк достаточно эффективно реализованы, что в .Net, что в JVM сейчас).

И, в большинстве случаев, сложность доступа будет O(1) или близкая к ней (в среднем, что для данной задачи подходит). Так что у всего мира такая структура данных существует, а почему её нет у тебя - мне не известно.

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

И, в большинстве случаев, сложность доступа будет O(1) или близкая к ней (в среднем, что для данной задачи подходит). Так что у всего мира такая структура данных существует, а почему её нет у тебя - мне не известно.

У всего нормального мира тоже нет. Есть только у тех, кто либо не понимает значений терминов O(f(n)) и асимптотическая сложность, либо понимает, но слишком вольно трактует.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

У всего нормального мира тоже нет.

Я просто приведу тебе код.

Код будет на F#, но там ничего сложного: 

open System
open System.Collections.Generic


let l1 = [for i in 1 .. 1000000 -> i]
let l2 = [for i in 1000001 .. 2000000 -> i]

let l3 = [for i in 2000001 .. 4000000 -> i]
let l4 = [for i in 4000001 .. 6000000 -> i]

let l5 = [for i in 6000001 .. 10000000 -> i]
let l6 = [for i in 10000001 .. 14000000 -> i]


let h1 = HashSet<int>(l1)
let h2 = HashSet<int>(l2)
let h3 = HashSet<int>(l3)
let h4 = HashSet<int>(l4)
let h5 = HashSet<int>(l5)
let h6 = HashSet<int>(l6)

let s1 = SortedSet<int>(l1)
let s2 = SortedSet<int>(l2)
let s3 = SortedSet<int>(l3)
let s4 = SortedSet<int>(l4)
let s5 = SortedSet<int>(l5)
let s6 = SortedSet<int>(l6)


let hIn (s: 'a ICollection) l2 = 
    None <> List.tryFind (fun e -> s.Contains e) l2

Все таблицы поиска заранее подсчитываются, поэтому влияние сборщика мусора исключается.

Результаты для 1, 2 и 4 миллионов поисков для HashSet: 

> hIn h1 l2;;
Real: 00:00:00.060, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn h1 l3;;
Real: 00:00:00.123, CPU: 00:00:00.109, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn h1 l5;;
Real: 00:00:00.248, CPU: 00:00:00.250, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

Как видно 1кк поисков проходит за 0.06, а 4кк за 0.248. Так же рассмотрим случай, когда исходная таблица имеет 4кк элементов:

> hIn h5 l1;;
Real: 00:00:00.062, CPU: 00:00:00.062, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn h5 l3;;
Real: 00:00:00.125, CPU: 00:00:00.125, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn h5 l6;;
Real: 00:00:00.243, CPU: 00:00:00.234, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

Результаты аналогичны. Отмечу, что разброс по времени у меня получался на 0.01 максимум.

Лично я вижу чёткую линейную зависимость, что подтверждает сложность поиска в O(1) для хеш-таблиц, где есть хорошая хеш-функция. Понятно, что будут коллизии, но их появление, при хорошей хеш-функции это большая редкость, а, следовательно, среднее время поиска будет O(1).

P.S. выше я написал про O(n + m), это немного не так. Но не из-за скорости поиска элемента, а из-за особенностей построения хеш-таблицы, т.к. при большом кол-ве элементов она должна быть перестроена.

Ну и в догонку приведу ещё тесты для деревьев поиска (сложность поиска log2(n), т.к. SortedSet использует чёрно-красное дерево).

> hIn s1 l2;;
Real: 00:00:00.189, CPU: 00:00:00.187, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s1 l3;;
Real: 00:00:00.368, CPU: 00:00:00.375, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s1 l5;;
Real: 00:00:00.734, CPU: 00:00:00.734, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s3 l1;;
Real: 00:00:00.170, CPU: 00:00:00.171, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s3 l4;;
Real: 00:00:00.382, CPU: 00:00:00.390, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s3 l5;;
Real: 00:00:00.772, CPU: 00:00:00.781, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s5 l1;;
Real: 00:00:00.176, CPU: 00:00:00.187, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s5 l3;;
Real: 00:00:00.358, CPU: 00:00:00.359, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false
> hIn s5 l6;;
Real: 00:00:00.802, CPU: 00:00:00.796, GC gen0: 0, gen1: 0, gen2: 0
val it : bool = false

Думаю из разницы во времени видно, что решение на хеш-таблице быстрее решения со сложностью поисковой части равное n*log2(n).

Norgat ★★★★★
()
Ответ на: комментарий от Waterlaz

Прочитай, пожалуйста, определение асимптотической сложности.

Рассмотрение входных данных большого размера и оценка порядка роста времени работы алгоритма приводят к понятию асимптотической сложности алгоритма.

Внезапо, именно разницу в сложности мои тесты и показывают (сравнивай рост hIn s5 l6 и hIn h5 l6 + независимость скорости hIn от h1\h5, где |h1| << |h5|). Внимательно просмотри их пожалуйста и перестань стоить из себя гения, а объясни, что же не так по твоему. Только без отсылок в далёкие дали книжек, т.к. никто не бросится их читать (а тесты приведены и указывают на то, что твои высказывания о n*log2(n) ложны).

Norgat ★★★★★
()
Последнее исправление: Norgat (всего исправлений: 1)
Ответ на: комментарий от Norgat

Внезапо, именно разницу в сложности мои тесты и показывают (сравнивай рост hIn s5 l6 и hIn h5 l6 + независимость скорости hIn от h1\h5, где |h1| << |h5|). Внимательно просмотри их пожалуйста и перестань стоить из себя гения, а объясни, что же не так по твоему. Только без отсылок в далёкие дали книжек, т.к. никто не бросится их читать (а тесты приведены и указывают на то, что твои высказывания о n*log2(n) ложны).

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

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

В хеш таблице коллизии вполне себе могут все испортить.

Можно пример кода, где бы проявлялось серьёзное влияние коллизий? Ограничения просто: хеш-функция стандартная от string, язык исполнения, желательно, под платформы .Net или JVM.

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

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

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

Мы же говорим об оценке сложности. Теория говорит нам, что без коллизий никуда.

Waterlaz ★★★★★
()
Ответ на: комментарий от Norgat

Я ведь и не спорю, что на практике хеш таблицы работают хорошо. Так же как и quicksort работает хорошо, хотя в худшем случае дает n^2

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

Теория говорит нам, что без коллизий никуда.

Большая часть этой теории - полностью негодная штука, когда её пробуют применить к практике, т.к. создавалась для теоретической классификации. Вот асимптотические оценки из этой оперы и годятся лишь для грубой оценки (если я всё правильно помню, то основная задача а.о. это теоретическая классификация алгоритмам по классам, а не практическая оценка).

Имхо, тут нужно использовать приближение O(1) для оценки, т.к. в реальности мы получим именно его в подавляющем большинстве случаев. А вот если мы получим коллизии, то тогда и думать нужно будет (а получить их нужно ещё постараться).

Norgat ★★★★★
()
Ответ на: комментарий от Norgat

Большая часть этой теории - полностью негодная штука

А вы бы с суперхаккиллером1997 спелись

unC0Rr ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Совет по архитектуре
Development
Как узнать, под какими дефайнами находится код? →