Как сделать запрос диапазона - PullRequest
Новая
       16

Как сделать запрос диапазона

1 голос
/ 08 марта 2010

У меня есть несколько временных меток, которые я хочу сравнить с диапазоном, чтобы увидеть, соответствуют ли они определенному диапазону дат. В основном, как между ... и ... совпадают в SQL. Очевидной структурой данных будет B-дерево, но, хотя в CPAN существует несколько реализаций B-дерева, кажется, что они реализуют только точное соответствие. Беркли DB имеет ту же проблему; есть индексы B-дерева, но нет соответствия диапазону.

Какой самый простой способ сделать это? Я не хочу использовать базу данных SQL, если мне не нужно.

Уточнение : у меня их много, поэтому я ищу эффективный метод, а не просто grep для массива.

Ответы [ 3 ]

3 голосов
/ 09 марта 2010

grep будет быстрым, даже на миллион из них. 

# Get everything between 500 and 10,000:

my @items = 1..1_000_000;
my $min = 500;
my $max = 10_000;

my @matches = grep {
  $_ <= $max && $_ >= $min
} @items;

Запустите под time Я получаю это: 

time perl million.pl 

real    0m0.316s
user    0m0.210s
sys 0m0.070s
2 голосов
/ 08 марта 2010

Временные метки - это числа. почему бы не распространенные операторы числового сравнения, такие как> и <? </p>

Если у вас много временных меток, проблема не отличается, если вы просто хотите отфильтровать ваш набор один раз . Это O (n), и любой другой метод будет длиннее.

С другой стороны, с огромным набором, из которого вы хотите извлечь множество различных диапазонов, было бы более эффективно сначала отсортировать элементы. Назовите номер поиска m, сложность прямой фильтрации будет O (m.n). При сортировке с последующим поиском это может быть O (n.log (n) + m.log (n)), что обычно намного лучше.

Подойдет любой метод сортировки O (n.log (n)), включая использование встроенного оператора сортировки (или b-дерева, как вы предложили). Основное различие между эффективными методами сортировки заключается в том, может ли ваша память хранить ваш полный набор или нет. Если у вас есть загрузочное место памяти, чтобы хранить в памяти и данные, и ключи (временные метки), вы можете хранить только временную метку и некоторый индекс для данных в памяти и реальных данных в другом месте (файл диска, база данных). Но если ваш набор данных действительно такой большой, наиболее эффективным решением, вероятно, было бы поместить все это в базу данных с отметкой времени и индексировать ее (привязка к базе данных очень проста с использованием perl).

Тогда у вас будет свой диапазон. Вы просто используете двудольный поиск для поиска индекса первого элемента, включенного в диапазон, и последнего, сложность будет O (log (n)) (если вы выполните линейный поиск, вся цель сортировки будет побеждена).

Ниже приведен пример использования sort и binary_search для массива временных меток, расширение использования некоторой структуры данных с временной меткой и содержимым оставлено в качестве упражнения. 

use Search::Binary;

my @array = sort ((1, 2, 1, 1, 2, 3, 2, 2, 8, 3, 8, 3) x 100000);
my $nbelt = @array;

sub cmpfn
{
    my ($h, $v, $i) = @_;
    $i = $lasti + 1 unless $i;
    $record = @array[$i||$lasti + 1];
    $lasti = $i;
    return ($v<=>$record, $i);
}

for (1..1){
    $pos = binary_search(1, $nbelt, 2, \&cmpfn);
}
print "found at $pos\n";
1 голос
/ 08 марта 2010

Я не использовал это. Но нашел это при поиске CPAN. Это может обеспечить то, что вы хотите. Вы можете использовать Tree :: Binary для построения ваших данных и подкласс Tree :: Binary :: Visitor :: Base для выполнения запросов диапазона.

Другой простой способ - использовать SQLite.

...