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

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

Вход:

"1011"
"0111"
"0111"

Вывод:

[1,2,3,3]

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


python string loops for-loop binary
person BGa    schedule 14.03.2019    source источник

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

person RmbRT    schedule 14.03.2019
comment
Спасибо за ваш ответ. Я знаю, что мне нужно как-то проверить все символы, но я не уверен, оптимально ли использовать 2 простых цикла for. Возможно, было бы лучше сказать преобразовать все строки в массивы numpy, а затем просто сложить их все. - person BGa; 15.03.2019
comment
@BGa Даже если вы это сделаете, ничего не изменится в том факте, что каждый символ (или бит) каждой строки должен быть доступен один раз. Таким образом, у вас все еще есть асимптотическая сложность O (N · k) , где N - количество строк, а k - длина строки. Обратите внимание, что в теории сложности O (n) совпадает с O (1000n + 10000), поскольку постоянные коэффициенты просто игнорируются. - person RmbRT; 15.03.2019