Самый быстрый способ определить, находится ли целое число между двумя целыми числами (включительно) с известными наборами значений
Очевидно, что файл слишком велик, чтобы его можно было сразу считывать в память.
Почему бы просто не использовать:
with open("data.txt") as myfile:
for line in myfile:
do_something(line.rstrip("\n"))
или, если вы не используете Python 2.6 и выше:
myfile = open("data.txt")
for line in myfile:
do_something(line.rstrip("\n"))
В обоих случаях вы получите итератор, который можно обрабатывать так же, как список строк.
EDIT: Поскольку ваш способ чтения всего файл в одну большую строку, а затем разделив его на строки новой строки, удалите новые строки в этом процессе, я добавил .rstrip("\n") к моим примерам, чтобы лучше имитировать результат.
5 ответов
Есть старый трюк, чтобы сделать это только с одним сравнением / ответвлением. Может ли это действительно улучшить скорость, может быть под вопросом, и даже если это произойдет, это, вероятно, слишком мало, чтобы заметить или позаботиться о нем, но когда вы только начинаете с двух сравнений, шансы на огромное улучшение довольно малы. Код выглядит следующим образом:
// use a < for an inclusive lower bound and exclusive upper bound
// use <= for an inclusive lower bound and inclusive upper bound
// alternatively, if the upper bound is inclusive and you can pre-calculate
// upper-lower, simply add + 1 to upper-lower and use the < operator.
if ((unsigned)(number-lower) <= (upper-lower))
in_range(number);
В типичном современном компьютере (то есть, в любом, использующем дополнение по два) преобразование в unsigned на самом деле просто нет - просто изменение в том, как рассматриваются одни и те же биты.
Обратите внимание, что в типичном случае вы можете предварительно вычислить upper-lower вне (предполагаемого) цикла, так что обычно это не дает значительного времени. Наряду с уменьшением количества команд ветвления это также (как правило) улучшает предсказание ветвления. В этом случае одна и та же ветвь берется независимо от того, находится число ниже нижнего конца или выше верхнего конца диапазона.
На практике этот метод переводит number и интервал в точку происхождения и проверяет, находится ли number в интервале [0, D], где D = upper - lower. Если number ниже нижней границы: отрицательно , а если выше верхней границы: больше, чем D .
Редко можно сделать существенную оптимизацию для кода в таком маленьком масштабе. Большой выигрыш в производительности достигается за счет наблюдения и изменения кода с более высокого уровня. Вы можете полностью исключить необходимость проверки диапазона или выполнить только O (n) вместо O (n ^ 2). Возможно, вам удастся изменить порядок тестов, чтобы всегда подразумевалась одна сторона неравенства. Даже если алгоритм идеален, выигрыш будет более вероятен, когда вы увидите, как этот код тестирует диапазон 10 миллионов раз, и вы найдете способ их пакетировать и использовать SSE для параллельного выполнения многих тестов.
Это зависит от того, сколько раз вы хотите выполнить тест на одних и тех же данных.
Если вы выполняете тест один раз, вероятно, нет никакого существенного способа ускорить алгоритм.
Если вы делаете это для очень ограниченного набора значений, то вы можете создать справочную таблицу. Выполнение индексации может быть более дорогостоящим, но если вы можете разместить всю таблицу в кеше, тогда вы можете удалить все ветвления из кода, что должно ускорить процесс.
Для ваших данных таблица поиска будет 128 ^ 3 = 2 097 152. Если вы можете управлять одной из трех переменных, поэтому вы рассматриваете все случаи, когда start = N одновременно, тогда размер рабочего набора уменьшается до 128^2 = 16432 байтов, что должно хорошо вписаться в большинство современных кэшей.
Вам все равно придется сравнить реальный код, чтобы увидеть, является ли таблица поиска без ответвлений достаточно быстрой, чем очевидные сравнения.
Этот ответ должен сообщить о проверке, выполненной с принятым ответом. Я выполнил тест с закрытым диапазоном для большого вектора отсортированного случайного целого числа, и, к моему удивлению, основной метод (low < = num & amp; num < = high) фактически быстрее, чем принятый ответ выше! Тест проводился на HP Pavilion g6 (AMD A6-3400APU с оперативной памятью 6 ГБ. Вот основной код, использованный для тестирования:
int num = rand(); // num to compare in consecutive ranges.
chrono::time_point<chrono::system_clock> start, end;
auto start = chrono::system_clock::now();
int inBetween1{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
if (randVec[i - 1] <= num && num <= randVec[i])
++inBetween1;
}
auto end = chrono::system_clock::now();
chrono::duration<double> elapsed_s1 = end - start;
по сравнению со следующим, который является принятым ответом выше:
int inBetween2{ 0 };
for (int i = 1; i < MaxNum; ++i)
{
if (static_cast<unsigned>(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1]))
++inBetween2;
}
Обратите внимание, что randVec является отсортированным вектором. Для любого размера MaxNum первый метод превосходит второй на моей машине!
Разве невозможно просто выполнить побитовую операцию над целым числом?
Поскольку оно должно быть между 0 и 128, если установлен 8-й бит (2 ^ 7), он равен 128 или более. Тем не менее, крайний случай будет болезненным, поскольку вы хотите провести инклюзивное сравнение.