Помогите понять код на Питоне

   # threshold by cover threshold
   thresholded = zip(*numpy.where(probabilities >= self.cover_threshold))

   # for each point, assign all other covered points
   # make sure that each point covers at least itself
   covering = [set((i,)) for i in range(N)]
   for x,y in thresholded:
     covering[x].add(y)

   # greedily add points that cover most of the others
   covered = set()
   universe = set(range(N))
   self._extreme_vectors = []
   self._covered_vectors = []
   while covered != universe:
     # get the point that covers most of the other points that are not yet covered
     ev = numpy.argmax([len(c - covered) for c in covering])
     # add it to the set of covered points
     self._extreme_vectors.append(ev)
     # add the covered points. note that a point might be covered by several EVs
     self._covered_vectors.append(sorted(covering[ev]))
     covered.update(covering[ev])
Это вход для него:
>>>probabilities
array([[1.00000000e+00, 1.56895075e-09],
      [3.13114925e-06, 1.00000000e+00]])
>>> self.cover_threshold
0.7
Это выход:
>>>self._covered_vectors
[[0], [1]]
>>> self._extreme_vectors
[0, 1]

Может кто-то пояснить, что этот код делает простым языком.

Похоже на какую-то странную реализацию жадного алгоритма, но я не могу понять этот код.

Мое предположение, что он тупо раскидывает номера индексов единиц по строкам в массивы одномерные. Но не уверен.

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Дозволені теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

> universe = set(range(N))
У автора топика должно горетьне из-за ЯП, а из-за самого кода. После вышепреведенной строки я перестал читать, ибо это ж адище.

считаю, что со строкой всё в порядке.
Поясните, чем она вас не устраивает?

В общем, оно на вход принимает coverage-матрицу — probabilities, где probabilities[i][j] — это «вероятность» того, что i-й элемент «покрывает» j-й. Далее будем считать, что i-й элемент покрывает j-й, если такая вероятность >= cover_threshold. Далее итеративно на каждом шаге в качестве ev выбирается элемент, который покрывает наибольшее количество ранее непокрытых элементов и записывается в self._extreme_vectors, а в self._covered_vectors идет лист всех элементов, которые покрывает ev (включая элементы возможно покрытые ранее).

Вот более оптимальная и понятная реализация на питоне:
github.com/...​aster/coverage_problem.py
Интересно было бы взглянуть на реализацию этой штуки на плюсах «в пять строк»)

венгерский алгоритм

Раньше я слышал о так называемой «венгерской математике» (синоним математики второго сорта), оказывается есть еще и «венгерские алгоритмы»)

Раньше я слышал о так называемой «венгерской математике» (синоним математики второго сорта),

Хм. Мне стало интересно, и я погуглил это выражение. Нашёл два варианта применения:
1. «Вторая — это как бы античная математика в наше время. Задаются простые по своей формулировке вопросы, и ищутся на них ответы. Насколько часто можно добиться совпадения попарных расстояний среди растущего числа точек на плоскости? Какими фигурами можно замостить плоскость? И тому подобное — вопросы, задаваемые „от балды“ и лежащие на поверхности.»
Я не вижу в этом ничего второсортного: это примерно тот же пласт вопросов, что великая теорема Ферма, гипотеза Гольбаха и т.п., которые реально создают целые новые области математики при попытках их решения (даже если окажется неудачным, как в случае континуум-гипотезы).
2. Примерно то же самое, но в резко негативном ключе и в основном от некоего юзера sowa из России, активного участника типичных дискуссий россиян, в которых позицию конкретной стороны просто невозможно понять без ящика водки и где стороны могут одновременно обвинять друг друга в недостатке и избытке либерализма (или какого-то другого -изма, но чаще всего таки этого) и в которых главное — напустить как можно больше цинизма в рассмотрении любого вопроса (по сравнению с которым пелевинский Саша Бло будет просто младенцем).

Если вы набрались второго, то я могу только пособолезновать, но лично от себя рекомендую не высказывать такие позиции в любом реально цивилизованном обществе. Независимо от темы, но подход незабвенных tyt.bce.hacpem это не то, что следует даже просто показывать на людях за пределами специально отведённых для того мест.

Cуть проблемы: есть n множеств (некоторые возможно пересекаются), из этих n множеств надо выбрать только k, таким образом, что бы количество разных элементов в их объединении было максимальным. Тривиальный пример, A = {0, 1}, B = {1, 3}, C = {1, 2, 3}; k = 2; Решение — A, C, так как AUС = {0, 1, 2, 3}, любое другое объединения двух множеств из A,B,C вложено в AUС. Или еще пример A = {1, 2, 3}, B = {2, 4}, C = {5, 6}; k = 2; Решение A, C, так как количество разных элементов в AUC больше чем в AUB и BUC. Далее в статье приводится формальное определение задачи в терминах целочисленного линейного программирования. Далее приводится жадный алгоритм (собственно реализация похожей штуки — в шапке темы), суть — итеративно на каждом шаге выбирается такое множество, которое содержит максимальное количество элементов, которых нету в ранее выбранных множествах. Далее приводятся постановки более общих формулировок проблемы.

а что тут сложного.

[set((i,)) for i in range(N)]

вот это аналогично циклу

ar = array() for (i=0;i<N; i++){ ar.push(set((i,))); }
да, python-way.
Получается чтото типа такого
[set([0]), set([1]), set([2]), set([3])]
где — set — множество(поддерживает всякие сравнения, пересечения и так далее).

Что делает весь код затрудняюсь ответить, но похоже выполнение за O(N^3)
Какието вектора собирает по покрытию чтоли. Расстояние вычисляется для всех элементов.

Eigen.

Рука тянется к револьверту.

Возможно увидеть реализацию на С++? Интересно увидеть разницу в объеме кода.

Питон для разрабов с достаточно прямыми руками чтобы писать без типов. Питон яро способствует говнокоду, но это не повод называть его плохим языком. Зачем академикам учить С++ когда можно писать на языке который не нужно знать чтобы писать на нём?

А ты думаешь, хороший язык назовут именем цирка? Как и многое другое, ныне здравствующее, писался изначально для малюсеньких программ и скриптов, дабы сделать их [внезапно] удобочитаемыми. А превратился в монстра. Хотя его по-прежнему любят писатели плагинов и маленьких программулек в среде больших программных пакетов. Иначе говоря, у него роль VBA — ну и производительность и оптимальность соответствующая.

И кому ты, такой умный, достанешься?

Хороший язык это который назвали дубом, потом чашкой кофе, марка которого называется как остров где выращивают чай?

Чтоб назвать тем же словом с суффиксом Script другой язык, в котором месяцы в дате нумеруются с нуля, а дни месяца — с единицы? Правильно было назвать WAT???

та я ж про то, что не название определяет «хороший» ли язык) А так js ещё тот уродец) Я бы предпочёл «Хуяк! и Скрипт» вместо WAT.

Ну по сравнением с языком в честь цирка он имеет одно заметное на сейчас преимущество: он компилируемый в машкод (даже если через JIT). Вон вчера очередная диверсия вылезла у Intel. Рост мощностей реально остановился, а аппетиты программ растут.

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

Засовывать в процессор не обязательно. А вот перейти на SRAM — таки поможет выбросить кэши памяти за ненужностью (или сократить до одного мелкого L1, и не жалеть его сбрасывать при любом подозрении). Ну да, всего-то раз в 10 дороже.

А не пофиг на эти «диверсии».

Таки не пофиг, если у тебя одна страница браузера начнёт из другой воровать данные.

Ну так при нынешней архитектуре компов или тормозить или воровать. Другого нет.

Не обобщай, и не обобщим будешь.
«Нынешняя архитектура» это сотни отдельных решений, из которых к воровству данных имеет отношение в основном тайминг кэшей.

И чем тебе SRAM поможет, если по шине не пропихнешь?

С чего это ты решил, что не пропихну?
Когда строка DRAM уже открыта, её чтение/запись происходят на охрененной скорости — сейчас это уже может быть 10GB/s и выше. Тут даже может оказаться, что SRAM надо ускорять под такие возможности...

аналогичное на матлабе

Скільки зараз ліцензійна копія матлаба коштує?

Матлаб ок ;)

питон провоцирует писать уродливый код

Ага, а також наші дороги провокують водіїв їздити по-мудацьки. Знаю цю пісню.

це якась математика, тре знати матан, щоб поняти що воно робить,
а без контексту важко догадатися,
мо’ накладання фільтрів на зображення, чи що?

P.S.
С++ давай досвіданья?

а шо то є, векторна алгерба?

накладання векторів для визначення існування кореляції, чи що?
ти ж звідкісь цей код вицарапав же...
я можу зараз запостити код Rust та сказати, чуваки, а що цей код робить?

можна просто в лоб переписати і не паритися без розуміння що саме робить, але кода буде раза в 3 більше на С++

for x,y in thresholded:

перебір по кортежу (аля цикл в циклі)
далі до елемента covering з індексом х робить add() - що саме значить це add(), тяжко сказати, чи то додає (с розумінні 1+1=2), чи прибавляє елемент, збільшуючи кількість елементів в контейнерів

може і так, а може і ні, я максимум парсилки логів робив на пайтоні

щод zip то
www.programiz.com/...​ming/methods/built-in/zip
навіть не знаю, що в С++ може таке бути

Загалом на пайтоні можна захерачити логіку в кілька строк, яку в С++ прийдеться розгортати в простині кода

строк 5 на С++

напишеш покажеш, мені цікаво, наскільки плюси високоабстрактнулися

update:
The set add() method adds a given element to a set if the element is not present in the set

короче, вектор перетворюеться в кортеж, кортеж в мапу, мапа ....якийсь піздець

це в тебе ще С++ головного моску, лікується жабаскриптом, але з послєдстієм JSголовного моску :)

о.к.
що цікавого взнав, що є «броненосець» для матана на С++
тему можна закривати,
всім дякую

Просто останнім часом пішла мода на статік стронг

Просто ВНЕЗАПНО оказалось, чтобы писать что-то большое на динамике, нужно покрывать все это уймой тестов, в том числе и проверку типов. А раз так, то зачем динамические языки вообще нужны, пусть лучше вон компилятор баги словит.

на Quora пишуть, що вже нема С++,
а є:
С++98
С++03
С++11
С++14
С++17
буде
С++20
С++23 і т.д.
і да, вже не буде хідерів, а буде як в расті — модулі... не той С++ і Дніпро вже не той і Київ не такий як 20 років тому

ніт, дуже багато синтаксичного цукру, майже весь буст і ще багато чого перелізло, тобто то навіть не діалекти С++, а різні мови

T*, T&, T&&, auto_ptr, shared_ptr, unique_ptr, weak_ptr, boost::memory_bullshit, мне дальше продолжать рассказывать о незапрещённом количестве вещей сделать одно и то же но совсем по разному? Если вот эта вся зашкварная солянка в одном проекте, то это хана тому кто будет его поддерживать.

T*, T&, T&&, auto_ptr, shared_ptr, unique_ptr, weak_ptr, boost::memory_bullshit
сделать одно и то же

Если у вас нет знаний о том, в чем тут разница — то это не значит, что эти все конструкты — одно и то же.
Учите матчасть.

Глобально, средства решения одной задачи — управления ресурсами. Это не означает что они делают одно и то же, они решают одну и ту же задачу, но ПО РАЗНОМУ, и это плохо.

«Глобально, все языки программирования решают одну задачу — сделать збс»

Вы вообще понимаете, что вы сморозили высокодуховную глупость?

скільки надо годов шоп виучить модерний С++17?

А так С++ сейчас стал отличным языком

Балшит. С++ ВСЕГДА был есть и будет охапкой граблей и костылей связанных многословной лапшой, ему так создатель в философии написал. Когда вы там уже сможете в компайлтайм рефлексию? А в нормальные дженерики которые не текстовый препроцессор? А в макросы которые работают с АСТ языка? А в линейные типы для контроля реурсов? А в код с запретом использовать низкоуровневые вещи типа голых указателей и ссылок? А когда вы уже сможете писать без кастов? А когда будут автоматическая деривация кодеков в другие форматы? А когда свои типизированные DSL? Ответ: никогда, Потому что

«... разрешать програмисту выбирать, пусть даже выбирать неправильно.»

Страуструп©.

А в нормальные дженерики которые не текстовый препроцессор?

Молодой человек, вы утомили. Темплейты тьюринг полны, в отличии от ваших дженериков.

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

Темплейты тьюринг полны

Тьюринг полнота — неверифицируемое зло. Везде где можно от неё отказатся, надо отказыватся. Дженерики были сделаны не Тьюринг-полными для нормальной работы тайпчекера, на который в С++ забили.

Тьюринг полнота — неверифицируемое зло

Так тьюринг полнота или текстовый препроцессор? А компилятор — это не текстовый препроцессор?

неверифицируемое

Зачем выкидаетесь терминами, которые не понимаете??? Причем тут верифицируемость к Тьюринг полноте? Учите матчасть, не копипастите из интернета вещи, которые не выучили.

Дженерики были сделаны не Тьюринг-полными для нормальной работы тайпчекера, на который в С++ забили

Т.е. темплейты таки круче дженериков? Отлично, хоть чему-то вы сегодня научились.

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

Учите матчасть

Как раз эту матчасть я знаю, это те элементарные вещи которые в университетах рассказывают.

не копипастите из интернета вещи, которые не выучили

Если вы считаете слова создателя языка бредятиной, то мне жаль ваш язык.

плюсы язык со статической типизацией

С с жалким подобием. Вот что такое статическая типизация: ru.wikipedia.org/wiki/Система_F. В С++ её нет. Тьюринг полнота имеет прямое непосредственное отношение к верифицируемости — любой тьюринг полный язык считает всё то же что и машина тьюринга и обратное тоже верно, а как известно из теории КН, не существует программы которая бы доказала заданное утверждение для произвольной программы. из этого следует, что это же верно и для С++. А вот если отбросить тьюринг полноту — построить такую программу можно. Вон в SQL так сделали (гарантия на отсутствие бесконечных циклов ценой обеднения языка), и по этому он стал достаточно надёжным.

Верифицируемость = АВТОМАТИЧЕСКОЕ(программа) умение доказывать (формально правилами переписывания к тождественно верному утверждению) соответствие программы требованиям. В С++ на неё положили болт настолько крупный и фундаментальный, что без специального софта для формальной верификации любая программа на С++ является сборником багов, сколько тестов для неё не пиши.

Т.е. темплейты таки круче дженериков

По сему Тьюринг полнота != крутость. А вот надёжность(верифицируемость) и лаконичность == крутость.

И синьорам помидорам это необходимо знать.

Когда у же вы поймёте что для каждой задачи нужно создавать свой тьюринг не-полный верифицируемый dsl и сдвигать все баги к одному очень узкому скоупу интерпретатора dsl?
Или по вашему segmentation fault/stupid exception зато быстро лучше? Лучше дохнуть с отладкой упоротых асинхронных багов на ручной синхронизации или использовать IO и эффекты?

впарить джаву

в топку джаву, я говорю о нормальных ЯП разряда хаскеля с хорошей системой типов. Но и JVM это уже достижение по сравнению с С++ — он предоставляет очень высокую степень гарантии отсутствия потери контроля над ячейкой памяти. А ваш С++ этого никогда не умел и не заумеет.

С с жалким подобием. Вот что такое статическая типизация: ru.wikipedia.org/wiki/Система_F.

Нет, вы таки учите матчасть. Есть дихотомия динамическая---статическая типизации. А «жалкое подобие» математическим термином не является

Тьюринг полнота имеет прямое непосредственное отношение к верифицируемости — любой тьюринг полный язык считает всё то же что и машина тьюринга и обратное тоже верно, а как известно из теории КН, не существует программы которая бы доказала заданное утверждение для произвольной программы

Шта. Какое-такое «заданное утверждение». Вы опять спутали с проблемой останова и даже не задумались на секундочку, что (почти) все языки программирования тьюринг полны.

Вон в SQL так сделали (гарантия на отсутствие бесконечных циклов ценой обеднения языка), и по этому он стал достаточно надёжным.

Шта еще за «надежный язык»?

Верифицируемость = АВТОМАТИЧЕСКОЕ(программа) умение доказывать (формально правилами переписывания к тождественно верному утверждению) соответствие программы требованиям.

Для разговорной речи такое определение подойдет.

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

Голословное утверждение, не подкрепленное фактами.

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

По сему Тьюринг полнота != крутость. А вот надёжность(верифицируемость) и лаконичность == крутость.

Бред.

Когда у же вы поймёте что для каждой задачи нужно создавать свой тьюринг не-полный верифицируемый dsl и сдвигать все баги к одному очень узкому скоупу интерпретатора dsl?

Не нужно.

Или по вашему segmentation fault/stupid exception зато быстро лучше? Лучше дохнуть с отладкой упоротых асинхронных багов на ручной синхронизации или использовать IO и эффекты?

Сразу видно у вас отсутствие опыта

нормальных ЯП разряда хаскеля

А, ясно. Очередной хаскеллист. По статистике, через 5 лет хаскеллист осознает свои ошибки и становиться плюсовиком или растоманом

По статистике, через 5 лет хаскеллист осознает свои ошибки и становиться плюсовиком или растоманом

растоманом лутчше, плюси — моветон

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

Haxe умеет конвертироваться в Python, кстати. Можно писать на нормальном строго типизированном языке, с понятным синтаксисом и даже с null-безопасностью. Жаль, что почти никто про это не знает.

Підписатись на коментарі