1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

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

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

  1. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    У меня часто встречается задача сжирающая непомерное количество времени. Один расчет, завершившийся сегодня, длился 3.5 недели! К сути:

    Есть 2 массива данных, состоящие из идентификатора(строка) и приписанных ей "ключей" - числа 1-3FFFFFh. Формат хранения можно организовать любой. На выходе нужно иметь таблицу вида ID1 ID2 Tan, где Tan - коэффициент Танимото, считающийся по формуле Tan = c/(a+b-c), я еще добавляю *100, получая проценты(это не принципиально). Здесь a и b - количество "ключей" для ID1 и ID2, соотвественно, а c - количество одинаковых "ключей". Если интересно могу подробнее написать для чего это делается :-)

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

    Код (Text):
    1.    
    2.     mov       ebx, 4
    3.     mov       eax, [esi]
    4.     xor        ecx, ecx
    5.     mov       edx, [edi]
    6.     jmp       @F
    7. align   16
    8. @@:
    9.     cmp       eax, edx
    10.     mov       eax, 0
    11.     mov       edx, eax
    12.     cmovbe  eax, ebx
    13.     cmovae  edx, ebx
    14.     add       esi, eax
    15.     add       edi, edx
    16.     add       ecx, eax
    17.     mov      eax, [esi]
    18.     add       ecx, edx
    19.     sub       ecx, 4
    20.     mov      edx, [edi]
    21.     or         eax, eax
    22.     jz         @F
    23.     or         edx, edx
    24.     jnz       @B
    25. @@:
    26.     shr       ecx, 2
    Здесь на входе ESI и EDI указывают на массивы ключей(завершенные 0), на выходе ECX - искомое число.

    Что здесь можно сделать еще для оптимизации по времени?
     
  2. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Забыл добавить - ключи отсортированы по возрастанию.
     
  3. KeSqueer

    KeSqueer Сергей

    Публикаций:
    0
    Регистрация:
    19 июл 2007
    Сообщения:
    1.183
    Адрес:
    Москва
    Как понял я, существует один массив идентификаторов и один массив ключей. Но
    поставило меня в тупик. Получается 2 массива ключей?
     
  4. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Не совсем так. Два массива идентификаторов, где каждый идентификатор ссылается на собственный массив "ключей". Соотвественно приведенный фрагмент относится к моменту сравнения, и ESI, EDI указывают уже на массивы ключей для 2 идентификаторов.
     
  5. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.924
    лучше оформить вывод Tan в двумерную таблицу ID1/ID2
     
  6. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    Serg50
    Для оптимизации этого кода очень желательно знать ожидаемое количество множеств, сколько в них элементов(хотя бы в среднем). Если множества небольшие, то есть смысл вычислять результирующую матрицу блоками, чтобы обрабатываемые множества помещались в кеш, это может ускорить алгоритм раза в 4.
     
  7. Serg50

    Serg50 New Member

    Публикаций:
    0
    Регистрация:
    17 фев 2010
    Сообщения:
    48
    Задачи где это используется разные, но наибольшего внимания заслуживает со след. параметрами:
    ID1: 50 000 - 700 000
    ID2: 500 000 - 1 500 000
    "ключей" на каждое ID: 1-600, среднее 70-100

    Как видете двухмерная матрица будет очень большой :-) Да и как правило она не нужна, так как результать это набор ID1 где Tan больше, или меньше(в зависимости от цели) чем заданное число.
     
  8. PSR1257

    PSR1257 New Member

    Публикаций:
    0
    Регистрация:
    30 ноя 2008
    Сообщения:
    939
    Serg50

    А в момент генерации ключей нельзя сразу сравнивать и подсчитывать? Не накапливать два массива?
     
  9. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    Serg50
    Можно связять каждый ID с разреженным битовых хешем. Чтобы хеш был разреженным, его длину нужно выбрать в несколько раз большей, чем среднее количество ключей. Из каждого ключа мы получаем индекс бита в нашем хеше и устанавливаем его в 1, а остальные биты остаются равными 0. Если два хеша проксорить, то количество единичных бит даст нижнюю оценку числа элементов в симметричной разности множеств, и если она больше (a+b)*(1-Tan)/(1+Tan), значит c/(a+b-c)<Tan, а если нет, то придётся сравнивать сами множества.
    Можно построить немного другой хеш, в котором число совпадающих бит для двух ID будет пропорционально числу общих элементов, но это в среднем. Сравнение с Tan жесткое или вариант "найти почти все" тоже годится?
     
  10. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.474
    Адрес:
    Russia
    Массивы уже отсортированы? Это прекрасно: тогда сортировка слиянием+подсчёт парных элементов (они будут идти друг за другом).
     
  11. Black_mirror

    Black_mirror Active Member

    Публикаций:
    0
    Регистрация:
    14 окт 2002
    Сообщения:
    1.036
    CyberManiac
    Слияние 10^11-10^12 массивов по 100 элементов в каждом? А оптимизация где? :-)
     
  12. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    CyberManiac
    А приведенный в первом посте код хоть и кривой, но как раз и реализует слияние... только без слияния :-), а сразу с подсчётом парных элементов.
     
  13. qqwe

    qqwe New Member

    Публикаций:
    0
    Регистрация:
    2 янв 2009
    Сообщения:
    2.914
    Serg50
    плохо понял проблему, но я бы решал ее с помощью разреженного вектора размерностью в максимальный номер ID. 4 метра - это не так много.

    void getABC(int* ID1, int* ID2, int* a, int* b int* c){
    char* v = malloc( 0x3fffff );
    memset(v, 0, 0x3fffff);
    for(*a = 0; *ID1 != 0; ID1++, *a++){
    v[*ID1] = 1;
    }
    for(*b = 0, *c = 0; *ID2 != 0; ID2++, *b++){
    // если в самих ключах одного ID2 нету повторов или их не надо учитывать.
    // тут можно и просто
    // *с += v[*ID2];

    // если же есть, то
    if(v[*ID2])
    *c++;
    v[*ID2]++;
    }
    }

    выделение памяти лучше вынести

    хотя, может я и не понял задания
     
  14. CyberManiac

    CyberManiac New Member

    Публикаций:
    0
    Регистрация:
    2 сен 2003
    Сообщения:
    2.474
    Адрес:
    Russia
    Black_mirror
    А вот это уже я должен спрашивать, только не "где оптимизация", а "где были мозги, когда плодили миллиарды массивов по сотне элементов в каждом".

    l_inc
    Да в том цодесе вообще без бутылки не разберёшься. Понятно, что интересен не весь супур-пупер массив, а только его кусочек из пары элементов на каждый момент времени. Хотя можно и целиком слить и на винт положить, если с парными ключами предполагается делать ещё что-то потом. Но более всего мне непонятно, как с 1.5 млн элементов в одном массиве и 700 тыс в другом можно обсчитывать пересечение этих массивов три недели. Даже если решать эту задачу дубовым SQL-запросом к какому-нить позорному MySQL, оно и то быстрее отработает.
     
  15. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    CyberManiac
    На винт — это ужасно. :-) Согласно задаче даже приведенный алгоритм с линейной сложностью и минимумом непредсказанных условных переходов даёт огромные задержки. Складывая массивы по 500 элементов на винт рассчёты затя-а-а-анутся... :-)
    Есть полмиллиона массивов ID1 и полмиллиона массивов ID2. Нужно попарно сравнить все массивы (ID1 с ID2). Длина каждого — в районе пары сотен элементов. По крайней мере я так понял задачу.
     
  16. t00x

    t00x New Member

    Публикаций:
    0
    Регистрация:
    15 фев 2007
    Сообщения:
    1.924
    оценка сверху даёт 700,000 * 1,500,000 * 600 ~ 6*10^14 ~ 500 Тбайт.
    или где-то закралась ошибка?
     
  17. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    t00x
    Это оценка чего? По смыслу почти подходит под трёхмерную двоичную таблицу, содержащую признаки присутствия конкретного ключа в обоих массивах ID. Если да, то о такой таблице нигде речь не идёт.
    Если же предполагалось посчитать объём обрабатываемых данных, то оценка сверху выглядит так:
    (700.000 + 1.500.000) * 600 ~ 1,3 ГБ.
     
  18. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    P.S. Хотя надо бы домножить ещё на 4, что есть размер одного ключа с учётом выравнивания размера числа "3FFFFF" до ближайшей большей степени двойки.
     
  19. qqwe

    qqwe New Member

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

    если нужно просто отмечать существует ли ключ N или нет, можно использовать способ

    char* keys;

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

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

    при этом используется блок памяти в (0x400000 >> 3) = 0x80'000 байт, что почти целиком влазит в кэш.
     
  20. l_inc

    l_inc New Member

    Публикаций:
    0
    Регистрация:
    29 сен 2005
    Сообщения:
    2.566
    qqwe
    А я не говорил хранении. Я говорил об объёме обрабатываемых входных данных. Хранятся ли эти данные где-то заранее или высчитываются динамически в процессе, известно вроде пока только автору.
    Лично мне ничего не нужно. :-)