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

Хммм... Сколько у вас ОЗУ? Хотя может за границы массива был выход... Надо индексы проверить.

 

Serg50
в детстве любил химию. дома всё облезло от паров йода.

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

любое сложное дело - еще та головоломка. программирование тут не исключение

откуда мне знать ваш алгоритм? вы разве его приводили?

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

Код (Text):

1. char map[maxid];
2.  
3. void getABC(unsigned int* ID1, unsigned int* ID2, int* a, int* b, int* c){
4.   int id;
5.   memset(map, 0, maxid);
6.   for(*a = 0; *ID1 != 0; ID1++, *a++){
7.     id = *ID1;
8.     map[id] = 1;
9.   }
10.   for(*b = 0, *c = 0; *ID2 != 0; ID2++, *b++){
11.     id = *ID2;
12.     *c += map[id];
13.   }
14. }

как видите - тоже самое, но без упаковки
скомпилено с -O2 и запущено на том ще самом ноутбуке, что и в прошлый раз.
результаты по окончанию 100 тестов

как видите, среднее время стало более чем в 3 раза больше (0.05с против 0.18с). те, если ваш алгоритм всего на 30% быстрее этого, то в топку его. тем более, что тот, который имеет битовую паковку можно и еще ускорить.

(кроме того, можно воспользоваться более подходящей машиной. с бо'льшим объемом кэша(!это важно. не ядра, не i, а кэш))

я совершенно не понимаю о каких элементах вы говорите. насколько я понял из историй выше - надо подсчитать общее количество совпадений (c) в 2х массивах ключей (ID1 и ID2). что я и сделал. попутно считаются a и b, но это, скорей всего, мало влияет на скорость. хотя..

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

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

это тоже базовая техника для ускорения. все достаточно описано в учебниках

 

Ну вот, исправил, теперь всё работает как надо. У себя тестил на 2х массивах состоящих из 1 .. 150000 элементов каждый, в элементе содержится 200 подэлементов. Тест занял 35 секунд
Ссылка осталась та же, в выложенной версии сделал массивы из 1 .. 1500000 элементов.

 

Слово то затасканное, сейчас куда ни плюнь всюду менеджеры. Если уж вам так интересна моя должность, то лучше всего ее отражает английский термин - Chemistry Director. Можете считать менеджером, да хоть топ-менеджером, правда по зарплате этого не видно

А вот за это спасибо! Убедительно.

Похоже, что вам не приходилось писать статей? Это привычка - ведь я работую не один. Да и возню с этой задачей начинал не я, она мне досталась по наследству он нескольких предшественников. Я столкнулся с этим пару лет назад, и сделанное меня не впечатлило. Пришлось вспомнить ассемблер(после многолетнего перерыва), и я ее решил как смог, пусть не оптимально, но 2 года работает. А тут наткнулся на форум, и решил полюбопытствовать, а как было бы правильно. Не думал, что практические задачи здесь под запретом

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

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

 

Неа.. тоже самое. Да Delphi штука тонкая
Ладно не парься, дальше сам буду разбираться. Вот сейчас поинтересуюсь, что за зверь Packed array

 

Serg50

ну зачем так спешить? я только во вкус входить начал. пожалуйста

о. ну разве я не пророк? это типичный почерк менеджера - уверенное намерение зарабатывать на халявном чужом труде. а всякое "это только мое хобби!" и "а слабо?" - самые затасканные менеджерские макароны, что я слышал.
вообще, умение разводить народ: с одной стороны определяет профпригодность вас, с другой стороны ваше клеймо, ну а с 3тьей - источник вашего ограничения.

фигня фигня. немного изменил алгос как я говорил. думал (и писал), что получится ускорить в 1.5-2 раза, однако тест (условия те же. -O2, комп, компилер, тот же код за исключением некоторых изменений) показал

те, среднее ускорение по 100 опытам в сравнении с алгоритмом с битовой паковкой - около 10 раз (0.046с против 0.0039с). и более чем в 30 раз по сравнению с отсутствием битовой паковки (0.18с против 0.0039с)

теперь осталось учесть утверждение о среднем значении ключей в 200. думаю, еще немного ускорить получится

не. не умею говорить от себя. только в ответ. постоянно не попадаю в сферу компетентности собеседника(-ков)

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

одноплатные учебно-пром компы конца 80х/начала 90х?

 

ну если нравится продолжим
Однако отделим мух от котлет. Продолжение темы менеджеры-халява, я перенесу в Heap.

 

Serg50
Значит скорее всего у вас проблема. Должно быть написано в титле консоли: Massive compare by d2k9 v1.01
Но я думаю возможно это из-за того что бинарник х86 и больше 3Гб ему не положено. Можно на Си переписать, но ето только за вознаграждение. Главное я принцип описал, а дальше вы уже можете что угодно сами написать основываясь на алгоритме - 35 сек это вам не 3.5 недели
По ссылке обновил и выложил пример когда на один 0 меньше массивы.
"Massive compare by d2k9 v1.1"

 

Serg50
наиболее лёгкий способ:
1. конвертировать получаемый CSV файл в один файл базы данных (база на выбор, лишь бы поддерживала большие файлы) записями вида ключ, IDn;
2. проиндексировать по ключ (если автоматически не индексируется);
3. и считать, что захотите, запросами к этой базе.

 

t00x
а движок базы сравнивать это все должен не будет? таже петрушка, только уже в движке базы. проверьте

кроме того, тут нет точного соответствия. чел сравнивает спектрограммы. те его интересует процент совпавших ключей по целой куче эталонов чтоб понять чего они там насинтезировали.
до определения - вся работа стоит. те тема эта им должна быть неслабо нужна. обратите внимание - начал это "хобби" предшественник ТС. счас сам ТС "заувлекался", вспомнил х86 асм (точнее, изучил с 0, тк раньше знал он другой), переворотил несколько алгосов, проводил бенчи между ними (история про 30%).

ну а вермишель про "хобби" - обычная торговля. топ-менеджер, однако. (вспомните чела, что эксклюзивные слойты под бровзеры както тут предлагал попробивать ему за $100. тоже "хобби" называлось. и "забота о голодных студентах")

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

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

 

Serg50

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

 

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

 

Кому-то Калифорния покоя не даёт. Я тоже туда хочу, но не надо так явно свои комплексы показывать. ^)

 

Сравнил несколько подходов:
1. Приведенный изначально - сравнение слиянием
2. Битовый массив по аналогии с темой Black_Mirror
3. Тоже самое но с BTS/BTR-коммандами
4. Только с BTR
Коды части от 2 массивов ключей до Танимото в приложении. Получилось следующее:
1 2 3 4
Athlon 64 3500+ 2.2GHz 512K Cache 8.2s 10.3s 12.6s 11.4s
Intel Core 2 Q9300 2.5GHz 6M Cache 9.8s 6.2s 8.7s 7.9s

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

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

qqwe

Не беспокойся, я и со старым алгоритмом насчитал на полгода работы вперед