Нахождение количества общих элементов 2 массивов

дык и я не понимаю что за проблема с таким простым заданием? и

((с)CyberManiac)
впрочем, странные большие задержки, обычно, указывают либо на кривой алгос с реализующейся возможностью зацикливания, либо на ошибку со стеком приводящую к зацикливанию (более чем актуально, если писать на асме или форте или других стек-машинах), или просто зацикливание

в этом и сложность писания на асме. не синтаксис

 

Перед началом цикла сравнения можно вспомнить, что всегда выполняется неравенство Tan<=min (a/b, b/a), так что может оказаться, что нет необходимости считать c. Далее, зная пороговое значение Tan и учитывая, что Tan растёт вместе с ростом c, можно вычислить пороговое значение c и в случае его достижения прекращать цикл.

 

Вопросов много Так что немного подробнее:
Задача иемеет отношение к химии, а точнее к поиску новых лек. препаратов. Допустим мы имеем 2 набора химических соединений(зачастую виртуальных), и обозначим их как ID1' и ID2', однако поскольку молекулы гибкие они могут существовать в виде нескольких устойчивых состояний, которые расчитываются отдельной программой, что дает нам уже упоминавшиеся ID1 и ID2, и соотвественно Id в них не уникальные, и могут повторятся в соотвествии с количеством возможных конформаций(у меня ограничено 250). Далее другая программа уточняет стереохимию, минимизируя энергию, и выдает для каждой конформации набор признаков-"ключей"( например пронумерованы все треугольники между акцепторами протонов, донорами и пи-ароматическими центрами )). Эта же прграмма уже может сделать далее всю работу, кстати используя алгоритм близкий к предложенному qqwe, однако из-за того что там это организовано через интерпретатор внутреннего, Pascal-подобного языка, это делается очень медленно. К счастью она может экспортировать эти данные в формате CSV, чем я и пользуюсь. Этот CSV переводится в бинарный формат с удалением вырожденных коформаций(с одинаковыми ключами), и далее идет то с чего я начал. Это используется для решения задач 2 типов: поиск молекул сходных с неким заранее выбранным набором или наоборот, получение набора с максимально разнообразными свойствами. Потом выбранное делается физически Подход на мой взгляд спорный с точки зрения химии, и во многом зависящий от того насколько правильно выбран способ генерации признаков, но это уже другая история...

 

Этот алгоритм, если я правильно понял, я уже использовал в предидущей версии, и он оказался на 30% медленнее. Ведь после каждого сравнения в приходится, зачищать поле Может я не правильно понял идею, но у меня было нечто типа:
1. Для всех key у ID1n v[key] = 1
2. Для всех key у ID2m c+ = v[key]
3. Для всех key у ID1n v[key] = 0
4. к началу циклов n, m

Black_mirror если я правильно понял, ты предлагаешь нечто подобное, но в битовом варианте? Кстати один из вариантов ключей дает именно битовое множество, но там ключей меньше, и проблем со временем тоже не было

Ravager этот вариант я уже пробовал, и в некоторых вариантах я его использую, но в общем он не дает заметного выигрыша по времени.

CyberManiac Приведенные цифры относились к среднему расчету, а 3.5 неделе ушло на сравнение 5000000 с собой же То есть 5000000*5000000*(~100)/2.

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

 

Serg50

Вот тут я совсем удивлён. При сортировке слиянием потребовалось бы не 5000000^2, а 5000000*2 сравнений, сравнить 10 млн 32-битных целых - это минуты, но не часы, и уж тем более не недели. Здесь время теряется явно не в процедуре поиска совпадающих ключей.

 

Видно я плохо объясняю Возьмем предельный случай - у нас 1 ID1 и сранивается с другим ID2. Здесь то и похоже собака зарыта - сами то ID не сраниваются - это лишь обозначения. Сравниваются ключи приписанные к каждому, и в этом предельном случае число сравнений будет min( key1, key2).

Вот так выглядит структура единичного ID в файлах которыми я пользуюсь:

dd длинна записи
dd смещение ключей
dw размер строки ID в байтах
dw количество ключей
db ID, строка
db 0

dd key1
...
dd keyN
dd 0

вот эти key1..N и сравниваются. Во к ним то и применяется сортировка слиянием, а вовсе не к ID. Их сранивать бесполезно - это просто названия.

 

Serg50
если вам достаточно
1. Для всех key у ID1n v[key] = 1
2. Для всех key у ID2m c+ = v[key]

(что там за ID1n v[key] = 0, я не понял. видать, попытка ввести задержку для солидности)

то вам стоит воспользоваться подходом #19
char* keys;

устанавливаем ключ
keys[N >> 3] |= 1 << (N & 7);

сбрасываем ключ
keys[N >> 3] &= ~(1 << (N & 7));

получаем значение ключа (0 или 1)
val = (keys[N >> 3] >> (N & 7)) & 1;


смысл заключается в том, что озу гораздо медленнее проца. поэтому, при доступе к нему (кэш промахе) вы будете поимеете очень большую задержку. что более чем вероятно при условии разбросанных данных большого объема (объем кэша ограничен).
так как разбросанность мы существенно снизить не можем (разреженные таблицы - один из наиболее быстрых способов поиска), нам остается максимально ужать объем. те
char предпочтительнее чем int
а так как вас интересует только 1 бит, то стоит ужать и тут. в 8 раз по сравнению с char и в 32 по сравнению с int.

и ессно, в цикле поиска и сравнения должно быть минимум левых обращений к памяти. те их вообще быть не должно, тк сбросываться/перегружаться будет не один char или int, а целая линейка.

я понятно тут все написал?

(хотя продолжаю непонимать что у вас там считалось по 3 недели. даже полностью на перло-питоне считалось бы быстрее)

 

мой вам совет, напишите тоже самое на С. не на асме и не на ++ах. то, что у вас считается так долго - говорит о ошибке.

 

На С я не писал уже более 15 лет... Я его перекрасно понимаю, но если возьмусь писать, то ошибок наделаю еще больше

Я понял причину нашего взаимонепонимания. Недоразумение лежит в понятии "ключ", вы его воспринимаете как бит в числе в пределах 3FFFFF, а это не так. Ключ - это число в пределах 1-3FFFFFh, то есть если характеристику ID перевести в битовое представление то для его размещения нужно 100000h бит, на каждое ID! Поэтому данные хранятся в виде где для каждого ID перечисляются номера гипотетически выставленных битов.

)

В этом подходе я эмулировал эту гипотетическую битовую последовательность байтовым массивом char[100000h], и приведенное действие требовалось для очистки оного перед следующим сравнением.

Когда мы начинали возиться с этой задачей, ее нам считал один парень в Калифорнии, и он как раз пользовался Перлом. Так ему требовалась неделя расчета на кластере для задачи, которую я сейчас считаю за 5-6 часов. В принципе имеющаяся скорость меня уже устраивает - все считается на 4-ядернике на соседнем столе, где я запускаю 4 задачи в параллель. Он жрать не просит, а срочности нет. Да и 3-недельная задача - это разовый расчет, потом можно пополнять полученные данные быстрее.

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

 

Serg50
Сколько элементов в массивах, сколько ключей в элементе?

 

Уже писал Элементов 100000 - 1500000, а вот ключей по разному, до 200. Теоретически может быть вплоть до 3FFFFFh, но такую молекулу я себе не представляю

 

Serg50
Тогда что можно посоветовать. Во первых алгоритмическая оптимизация. Предварительно для каждого элемента генерировать отсортированное множество (ключ : кол-во). Во вторых распараллелить (cuda, ati stream, openCL и т.д).

 

Serg50

А можно пример массива ключей (не все, конечно - элементов 10-20). Как я понимаю, элементы массива сильно разрежены (посколько ключи от 1 до 3FFFFFh, а их всего ~200, то среднее расстояние между ними порядка ~3FFFFFh/200). Или же нет, есть какие-то "скученности"?

 

Есть, скорее как раз кучками и идут
Пример ID, ключи:
"A01230445", "32930 32994 33058 37010 37011 37020 37075 37076 98530 98595 102546 102547 102554 102556 102563 102611 102612 102626 103066 103122 135378 135386 135388 135444 135458 135899 135955 143570 143588 144083 144092 164066 164130 167954 167963 167972 168082 168083 168099 168147 168148 168154 168162 168218 168592 168664 168728 176274 176275 176282 176284 176291 176338 176784 176787 176794 176848 176852 180435 180451 180498 180952 180955 180962 181016 181019 181020 181978 182042 182043 184338 184531 184532 184595 184832 184860 185027 185091 185092 185875 186066 186131 186404 186588 186652 187139"

 

В таком случае (наверное) есть смысл попробовать сыграть на этом. Попробовать пропускать сразу кучку и идти далее.

Предположим, распределение ключей - это в среднем набор таких кучек с дисперсией (установить экспериментально?) и неким средним числом элементов в кучке.

Пусть мы обрабатываем начало кучи и это элемент Ka (Ka - первый набор ключей), также текущий данный элемент второго набора ключей - Kb[j]. Пусть среднее число элементов в куче (ожидаемое) равно D. Сначала пытаемся что-то оценить (неясно):

- Если Kb[j] >> (Ka+D*2..5), то есть хороший шанс что впереди в Ka идет сразу несколько элементов которые почти наверняка меньше Kb[j];
- Пытаемся определить большую границу кучи - смотрим что в элементе (нужно уточнить) Ka[i+D*2..5]. Если этот элемент также <Kb[j] - сразу пропускаем эту кучу (не всю возможно) и переходим от i к i+D*2..5.

Как-то так, нужно думать...

 

Serg50
Если уже отсортированы и нет повторов, то остаётся параллелить.

 

Ещё можно сделать массив размером 3FFFFFh элементов(или хеш таблицу), в котором хранить массивы указателей или индексов соответствующих ключей. То есть в первом элементе хранить массив индексов элементов, которые содержат единицу, и т.д. При проходе просматривать этот массив и делать соответствующие вычисления.

 

qqwe

а ещё чтение с жесткого диска никуда не девалось...(

 

Serg50

да нет. мы все прекрасно понимаем. для того, чтобы знать - есть такой ключ или нет - вам достаточно одного бита - 0=есть, a 1=нет.
хранить свои ключи вы можете в списке ключей, что привычнее. и в разреженной таблице размерностью в максимальный диапазон ключей, что даст значительный прирост в скорости при поиске и сортировке.

во втором случае в массиве вы храните не сами ключи, а по индексу == номеру ключа нужные вам признаки/ссылки связвнные с этим ключом. те, для получения этих признаков для определенного ключа вам достаточно
key_flags = map[key];

в вашем случае key_flags это просто признак существования такого ключа, те 1 бит. о чем я вам и писал

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

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

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

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

 

Как я говорил, этот метод я уже проверял, и он показал себя на 30% медленнее чем подсчет совпадений слиянием. Однако:

А вот это я не пробовал, мне показалось, что точечная очистка будет быстрее. Возможно зря Что то я встречал у Фогнера, что при соблюдении нек. условий rep stosd работает очень быстро. Набо посмотреть.

А вот здесь у меня явно не хватает знаний :-( Я не знаю как можно контролировать кэш. Где нибудь это можно посмотреть?

он это делал нам бесплатно