Java - большой O из bitCount ()?

Что такое большое число битов? Я не уверен, как работает этот метод, но я предполагаю, что он выполняется за O(logn).

В частности, с этим кодом (где x = 4, y = 1):

return Integer.bitCount(x^y);

java big-o bitcount
person data_pi    schedule 29.05.2017    source источник
comment
Что n в вашем O(log n)? Общее количество битов в целом числе? Говоря о Большом О, мы устанавливаем стоимость некоторой произвольной операции равной 1, и справедливо предположить, что bitCount имеет стоимость 1.   -  person Mephy    schedule 30.05.2017
comment
На самом деле я бы предположил, что это O(1), см., например. stackoverflow.com/questions/1458314 /   -  person jonrsharpe    schedule 30.05.2017

Ответы (3)


arrow_upward
6
arrow_downward

Учитывая его реализацию, метод состоит из шести операторов O(1), выполняемых последовательно, так что это O(1).

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}
person RedXIII    schedule 29.05.2017
comment
JVM может реализовать его иначе, чем код, который вы видите в исходном коде JDK, и на самом деле это так, поскольку это известная функция. Обычно он компилируется в одну инструкцию popcnt на платформах, которые его поддерживают (большинство интересных). Однако на самом деле это не меняет вывод (хотя это означает, что Integer.bitCount() и Long.bitCount() обычно занимают одно и то же время, что не было бы вашим выводом, если бы вы посмотрели на источник. - person BeeOnRope; 30.05.2017

arrow_upward
2
arrow_downward

Это O(1), вот его реализация для JDK 1.5+:

public static int bitCount(int i) {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}
person syntagma    schedule 29.05.2017
comment
На практике эта реализация не используется, потому что на большинстве платформ Integer.bitCount и несколько других простых методов в классах Integer, Long и т. д. реализованы как встроенные функции JVM, которые обычно приводят к созданию одной инструкции типа popcnt. Тем не менее O (1), хотя :) - person BeeOnRope; 30.05.2017
comment
Это звучит разумно, но можете ли вы указать какой-нибудь исходный код, который реализует это с использованием интристики JVM (я нашел исходный код, который использует именно вставленный код)? - person syntagma; 30.05.2017
comment
Да, вы должны копаться в исходном коде C++ JVM. Чтобы узнать, встроен ли метод, проверьте vmSymbols.hpp для вашей версии JVM и найдите имя функции. В этом случае вы найдете строку типа do_intrinsic(_bitCount_i, java_lang_Integer, bitCount_name, int_int_signature, F_S), которая указывает, что функция потенциально является встроенной. - person BeeOnRope; 30.05.2017
comment
На этом этапе вам придется копаться в источнике .cpp, чтобы увидеть, действительно ли он находится на интересующей вас платформе (обычно это так, как только вы найдете его в .hpp, но это может быть не так по нескольким причинам). например, отсутствие поддержки на той или иной платформе и т. д.). В случае с bitCount он обычно становится неотъемлемой частью интересующих современных платформ. Другой подход состоит в том, чтобы просто выполнить рассматриваемый метод в горячем цикле, а затем использовать что-то вроде perf top для проверки выполняемых инструкций. См. также этот вопрос. - person BeeOnRope; 30.05.2017
comment
Спасибо, это интересно. - person syntagma; 30.05.2017
comment
... и, поскольку я исчерпывающ, другой подход состоит в том, чтобы скопировать и вставить JDK в переименованную функцию, а затем сравнить исходную копию и точную копию. Если это нормальный, а не внутренний код, вы должны получить то же время. Я попробовал это сейчас, и для Integer.bitCount() я получаю ~ 2,0 миллиарда вызовов на bitCount в секунду, в то время как для точной копии кода JDK я получаю только 0,4 миллиарда вызовов в секунду. - person BeeOnRope; 30.05.2017
comment
@BeeOnRope Я не знал, что JVM может заменить существующую исходную реализацию. Охвачена ли концепция JLS? Кроме того, в чем именно разница между встроенными и нативными методами? - person shmosel; 30.05.2017
comment
@shmosel - насколько я знаю, все внутренние методы также имеют реализацию JDK, так что это общее правило. Реализация должна быть там, поскольку (а) не все платформы могут поддерживать встроенную версию (б) бывают случаи, когда встроенная версия не используется (например, в интерпретаторе) или при отладке и (в) в принципе исходный код JDK переносимым на реализации JVM, которые не встраивают вещи. Вы не найдете упоминания об этом в JLS — это на гораздо более низком уровне. Даже спецификация JVM не упоминает об этом. Это похоже на то, как компиляторы C++ распознают memcpy и часто заменяют его. - person BeeOnRope; 30.05.2017
comment
@shmosel - native методы очень разные. Это является частью спецификации JVM (вероятно, ключевое слово native также кратко упоминается в JLS) для реализации методов JNI. По сути, у вас есть C-подобная функция в каком-то двоичном файле, и эта функция вызывается, выполняет свою работу и возвращает результат. Существуют правила передачи параметров и многое другое. Он должен работать на любой платформе и т. д., хотя, конечно, вам нужно включать разные библиотеки для разных архитектур. - person BeeOnRope; 30.05.2017
comment
С другой стороны, внутренние методы сильно отличаются тем, что они заменены JIT в скомпилированном ассемблерном коде. Там нет нативного кода, и никакая функция не вызывается. Есть только несколько инструкций внутри реализации JIT-компилятора, которые говорят: эй, есть эта инструкция сборки popcnt, используйте ее, когда вы компилируете код, который использует Integer.bitCount. Накладные расходы фактически нулевые, в то время как вызовы native обычно имеют накладные расходы в 20 или более циклов. @shmosel - person BeeOnRope; 30.05.2017
comment
Вы можете думать о встроенных методах как о способе расширения байт-кода Java для охвата более примитивных операций без фактического расширения байт-кода (что делает его работоспособным). Байт-кода popcnt нет, но, сообщая JIT о специальных методах в классе Integer, он почти такой же, как и был. Некоторые методы в значительной степени должны быть реализованы как встроенные, например, методы в классах Atomic*: эти методы имеют ключевое слово native, но на самом деле они являются внутренними элементами... - person BeeOnRope; 30.05.2017

arrow_upward
0
arrow_downward

Любой алгоритм, работающий с входными данными ограниченного размера, имеет сложность O(1).

bitCount работает с вводом ограниченного размера.

Поэтому bitCount имеют сложность O(1).

person talex    schedule 06.07.2021