Подсчет единиц в наборе «двоичных строк» ​​(Python)

Question

У меня есть большой набор (100 000) двоичных строк (фиксированная длина k), например: «011100001111000010», «111011011110000100» и т. Д. Некоторые двоичные строки содержат начальные нули.Я хотел бы получить список L длины k такой, что a [i] = количество двоичных строк, имеющих 1 на i-м месте.Например:

Входные данные:

"1011"
"0111"
"0111"

Выходные данные:

[1,2,3,3]

Поскольку число двоичных строк очень велико (100000+) и k составляет около 100, используявложенные в циклы кажутся очень неэффективными.Что было бы наиболее эффективным (или, по крайней мере, более эффективным) способом решения этой проблемы?

Answer 1

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

Таким образом, вам придется использовать 2 цикла: один цикл по всем строкам и один внутренний цикл по всем символам в текущей строке.Затем просто увеличьте i-й счетчик, если строка имеет значение 1 в качестве i-го символа.

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