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

Тема в разделе "WASM.A&O", создана пользователем Serg50, 1 мар 2010.

  1. d2k9

    d2k9 Алексей

    Публикаций:
    0
    Регистрация:
    14 сен 2008
    Сообщения:
    325
    Хммм... Сколько у вас ОЗУ? Хотя может за границы массива был выход... Надо индексы проверить.
     
  2. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    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, но это, скорей всего, мало влияет на скорость. хотя..
    нет. объем ее делает дорогостоящей. только деньги можно вложить как в разработку, так и в закупку аппаратуры. железо будет дороже. сильно дороже. особенно если съэкономить на выплатах разрабам
    впервые встречаю человека называющего себя "мы", с удивительным постоянством озадачивающего своим случайным интересом то парней из калифорнии, то парней из россии (причем, совершенно без разницы на чем пишущих, главное результат), покупающих ради мелкого любопытства серьезную аппаратуру.
    вы б хоть кэтчупа к своим макаронам добавляли, чтоли

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

    d2k9 Алексей

    Публикаций:
    0
    Регистрация:
    14 сен 2008
    Сообщения:
    325
    Ну вот, исправил, теперь всё работает как надо. У себя тестил на 2х массивах состоящих из 1 .. 150000 элементов каждый, в элементе содержится 200 подэлементов. Тест занял 35 секунд :lol:
    Ссылка осталась та же, в выложенной версии сделал массивы из 1 .. 1500000 элементов.
     
  4. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Слово то затасканное, сейчас куда ни плюнь всюду менеджеры. Если уж вам так интересна моя должность, то лучше всего ее отражает английский термин - Chemistry Director. Можете считать менеджером, да хоть топ-менеджером, правда по зарплате этого не видно :)
    А вот за это спасибо! Убедительно.
    Похоже, что вам не приходилось писать статей? Это привычка - ведь я работую не один. Да и возню с этой задачей начинал не я, она мне досталась по наследству он нескольких предшественников. Я столкнулся с этим пару лет назад, и сделанное меня не впечатлило. Пришлось вспомнить ассемблер(после многолетнего перерыва), и я ее решил как смог, пусть не оптимально, но 2 года работает. А тут наткнулся на форум, и решил полюбопытствовать, а как было бы правильно. Не думал, что практические задачи здесь под запретом :)

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

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

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Неа.. тоже самое. Да Delphi штука тонкая :)
    Ладно не парься, дальше сам буду разбираться. Вот сейчас поинтересуюсь, что за зверь Packed array :)
     
  6. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Serg50
    ну зачем так спешить? я только во вкус входить начал. пожалуйста

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

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

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

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

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

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    ну если нравится продолжим :)
    Однако отделим мух от котлет. Продолжение темы менеджеры-халява, я перенесу в Heap.
     
  8. d2k9

    d2k9 Алексей

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

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.921
    Serg50
    наиболее лёгкий способ:
    1. конвертировать получаемый CSV файл в один файл базы данных (база на выбор, лишь бы поддерживала большие файлы) записями вида ключ, IDn;
    2. проиндексировать по ключ (если автоматически не индексируется);
    3. и считать, что захотите, запросами к этой базе.
     
  10. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    t00x
    а движок базы сравнивать это все должен не будет? таже петрушка, только уже в движке базы. проверьте

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

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

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

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

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Serg50
    съехать не получится. удача и неудовольствие, как утверждает лао-цзы связаны. съедете тут - что страшнее догонит. от всего не сбежать. про колобка читали?
     
  12. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Вы неправильно поняли. Я просто предлагаю отделить обсужение алгоритма/кода от "общих" дискуссий, и перенес в другую тему - см. WASM.HEAP - в самом низу общего списка. Мне кажется, что там это более уместно.
     
  13. Booster

    Booster New Member

    Публикаций:
    0
    Регистрация:
    26 ноя 2004
    Сообщения:
    4.860
    Кому-то Калифорния покоя не даёт. Я тоже туда хочу, но не надо так явно свои комплексы показывать. ^)
     
  14. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Сравнил несколько подходов:
    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
    Не беспокойся, я и со старым алгоритмом насчитал на полгода работы вперед :)