LINUX.ORG.RU

Попарные сочетания элементов всех списков

 ,


1

3

Дано: список из списков некоторых элементов. Требуется сгенерировать список пар из всех элементов разных списков между собой. Т.е., например, из списков (1,2,3) и (4,5) получится (1,4), (2,4), (3,4), (1,5),(2,5),(3,5)

Списков может быть много, количество элементов в них произвольным от 1 до бесконечности условно говоря.

Как бы поизящнее и побыстродейственнее сделать, а то алгоритм с 4-мя (четырьмя!!!) вложенными циклами как-то не очень приятно выглядит.

Базовый код примерно следующий:

list1 = ['1','2','3']
list2 = ['10','11','12','13']
list3 = ['20','21']
lista = [list1,list2,list3]
nl = len(lista)
cross=[]

for k in range(nl): # k - номер списка в lista, 0 ... len-1
    klist = lista[k]      
    for m in range(k+1,nl): #m - перебираем все последующие списки
        mlist = lista[m]
        for i in range(len(klist)): # Составляем пары элементов двух списков
            for j in range(len(mlist)):
                d2 = [klist[i],mlist[j]]
                cross.append(d2)

print(cross)

Результат:

[['1', '10'], ['1', '11'], ['1', '12'], ['1', '13'], ['2', '10'], ['2', '11'], ['2', '12'], ['2', '13'], ['3', '10'], ['3', '11'], ['3', '12'], ['3', '13'], ['1', '20'], ['1', '21'], ['2', '20'], ['2', '21'], ['3', '20'], ['3', '21'], ['10', '20'], ['10', '21'], ['11', '20'], ['11', '21'], ['12', '20'], ['12', '21'], ['13', '20'], ['13', '21']]
★★★★★

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

Ответ на: комментарий от praseodim

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

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

Спасибо, не знал про itertools.combinations хотя в этой реальной задаче он не сильно упрощает. Ладно, пока оставлю как есть, хотя и не нравится мне.

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

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

Я кстати похоже отупел сильно =) Чего-то хотел алгоритмического трюка для ускорения генерации, но совсем забыл, что количество пар в результате будет тем же и над ними надо будет произвести вычисления (там не перемножение, посложнее). Распараллелить естественно можно и даже нужно.

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

Реальная структура примерно такая: списков где-то несколько десятков тысяч, в каждом списке примерно от 1 до 40-50 (но в среднем 10-12, но не исключено и более 50) элементов, представляющих собой вектора из 1500 чисел. Для каждой пары векторов из разных списков вычисляется косинусное расстояние.

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

Чисто из любопытства: а что потом с этим набором полученных чисел планируется делать? Если даже есть несколько десятков тысяч списков (пусть 20 000), в каждом по 20 чисел (чисел, не векторов), то попарное что-угодно будет иметь 2е+4*(2е+4 - 1)*19 = 7.6e+9 чисел или пар. Как бы немало %)

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

а что потом с этим набором полученных чисел планируется делать?

Это применяется в системах машинного распознавания чего-либо (например, лиц для наглядности или авторов книг). Натренировал ты допустим модель на известных тебе классах, подсчитал для них точность ее работы. Все замечательно, но что делать для ситуации, когда ее надо применять потом для классов, на которых ее не тренировали?

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

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

Позволяет оценивать качество детекции какой-то распознавалки на неизвестных ранее объектах.

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

Но питон тут не вытянет очевидно, долго будет.

Смотря как его готовить. Для численных расчетов на питоне есть встроенная библиотека Numpy, написанная на C++. Содержит много чего, в частности, свои типы массивов и операций над ними. Есть еще Torch, который может считать как на CPU, так и на GPU.

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

Разве не делается это всё проще: собираете базу эмбеддингов (векторов) «известных» объектов. Потом смотрите расстояния от эмбеддинга объекта который надо классифицировать и выдаёте топ результатов из базы на что похож классифицируемый объект.

Если что, то таких движков есть уже и не надо ничего питонить.

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

Разве не делается это всё проще: собираете базу эмбеддингов (векторов) «известных» объектов. Потом смотрите расстояния от эмбеддинга объекта который надо классифицировать и выдаёте топ результатов из базы на что похож классифицируемый объект.

Это годится для поиска похожих объектов или классификации среди уже классифицированных.

Как при этом оценить точность и полноту классификации на заранее неизвестных объектах, классы которых не классифицировались? Я читал, что это как раз решалось подобным образом для систем распознавания лиц. То есть, есть система, натренированая распознавать 10k уже известных лиц, например. Как узнать насколько точно она будет распознавать неизвестные на момент тренировки?

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

Как ни готовь - нампай сливает вчистую плюсам по производительности. Чудес не бывает.

С чего ему сливать, если нампай и написан на C++? Какой-то оверхед от вызовов конечно есть, но все же.

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

Много чего, что на питоне записывается в пять-десять строчек, на том же C++ потребует сотню строк кода. Недавно в задаче на метеостанции сам же наглядно показал, быстро написав программку на питоне.

Так что фичи питона + нампай и торч (статистики еще пандас любят) и это в общем взлетело и неплохо взлетело.

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

Делали такое для пропускной системы.

Одна модель детектит лицо в кадре, вторая модель распознаёт его. Из qdrant’а поиском достаются эталонные изображения, наиболее близкие к результату работы второй модели. И всё.

На сотне тысяч эталонных эмбеддингов поиск работал шустро.

Как при этом оценить точность и полноту классификации на заранее неизвестных объектах, классы которых не классифицировались?

Как мне кажется - никак.

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

С чего ему сливать, если нампай и написан на C++?

С того, что оптимизаций толком нет и/или много проходов по циклу вместо одного.

Мне не очень хочется защищать питон

Не надо его защищать, мы с коллегами 20 с гаком лет юзаем связку питон-С++ для HPC. Просто не надо писать на питоне то, что априори должно делаться на плюсах.

Так что фичи питона + нампай и торч (статистики еще пандас любят) и это в общем взлетело и неплохо взлетело.

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

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

На сотне тысяч эталонных эмбеддингов поиск работал шустро.

Так ведь дело не в шустрости работы.

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

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

Как мне кажется - никак.

Ну вот собственно придумывают разные трюки с вероятностями.

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

Вам ведь все равно какой-то порог пришлось вводить?

Насколько помню, там было довольно резкое падение, т.е. (по памяти и совсем условно), для известных лиц 0.87 - 0.95 , для неизвестных больше 0.65 практически не было.

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

Как мне кажется - никак.

Ну вот собственно придумывают разные трюки с вероятностями.

А как же кроссвалидация? Как же стопицот разнообразных метрик уже давно придуманных для всевозможных частных случаев таких систем?

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

Решение на combinations + product уже дали. Но вообще в таком виде это (задача) что-то очень странное, тяжело распарсить, лучше было сформулировать исходную задачу, может там и не нужны никакие пары списков. //впрочем однострочник с reduce тоже хреново парсится

ei-grad ★★★★★
()
Последнее исправление: ei-grad (всего исправлений: 1)
Ответ на: комментарий от thunar
def pairwise_product(*args):
  for a, b in combinations(args, 2):
    yield from product(a, b)

assert list(pairwise_product(*lista)) == [
 ('1', '10'),
 ('1', '11'),
 ('1', '12'),
 ('1', '13'),
 ('2', '10'),
 ('2', '11'),
 ('2', '12'),
 ('2', '13'),
 ('3', '10'),
 ('3', '11'),
 ('3', '12'),
 ('3', '13'),
 ('1', '20'),
 ('1', '21'),
 ('2', '20'),
 ('2', '21'),
 ('3', '20'),
 ('3', '21'),
 ('10', '20'),
 ('10', '21'),
 ('11', '20'),
 ('11', '21'),
 ('12', '20'),
 ('12', '21'),
 ('13', '20'),
 ('13', '21')
]
ei-grad ★★★★★
()
Ответ на: комментарий от sshestov

7.6e+9

Ты примерно на порядок ошибся.

Всего пар будет n*(n-1)/2 - n, где n - общее количество всех векторов. Если n = 20000 * 20, то пар будет почти 80 миллиардов.

Как бы немало %)

Здоровья погибшим, как говорится.

anonymous
()