Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
Здравствуйте, busk, Вы писали:
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
Здравствуйте, busk, Вы писали:
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
не очень понятно, что вы хотите сэкономить. В том смысле, что безо всякого хеша проверка диапазонов на пересекаемость — это два сравнения и один and:
(A.Start <= B.End) && (A.End >= B.Start)
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
Ну записывай две даты в стрим и получай Хэш Взят отсюда
Здравствуйте, Serginio1, Вы писали: B>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. S>Ну записывай две даты в стрим и получай Хэш
И как теперь "сравнивая два хэша сказать, что они пересекаются"?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, busk, Вы писали:
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
Это невозможно. Доказательство от противного:
Предположим, что это возможно.
Тогда существуют два интервала с одинаковым хэшем но разными диапазонами лат.
Увеличим один из интервалов на один день.
Его хэш должен остаться тем же (чтобы соблюдалось условие проверки пересечения со вторым интервалом).
Но вместе с тем, хэш должен измениться, так как появился новый день, который может пересекаться с неким третим интервалом.
Получаем противоречие, то есть исходная посылка ("Предположим, что это возможно") не верна.
Вообще, с практической точки зрения хэш тут совершенно не нужен. Два сравнения по индексу по производительности и так будут будут летать.
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Serginio1, Вы писали: B>>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. S>>Ну записывай две даты в стрим и получай Хэш S>И как теперь "сравнивая два хэша сказать, что они пересекаются"?
Сравнивать конечные даты диапазона в которые они попадают.
На самом деле достаточно одной минимальной даты диапозона.
То есть ищется дата на max(Date) where Date<=CurrentDate
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали: S>>И как теперь "сравнивая два хэша сказать, что они пересекаются"? S> Сравнивать конечные даты диапазона в которые они попадают. S>На самом деле достаточно одной минимальной даты диапозона. S>То есть ищется дата на max(Date) where Date<=CurrentDate
Простите, но я этот поток не могу распарсить.
Вот вы предложили функцию для вычисления хеша от диапазона дат.
Допустим, нам известны диапазоны d1 и d2, а также их хеши h1 и h2.
Покажите код функции, которая определяет, пересекаются ли диапазоны:
public static boolean AreIntersecting(DateRange d1, DateRange d2, int h1, int h2)
{
if(SomeFunction(h1, h2))
{ /// вот тут мы типа ускоряем проверку благодаря использованию хешейreturn ???
} else// идём по "медленной" ветке return (d1.Start <= d2.End) && (d1.End >= d2.Start)
}
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vmpire, Вы писали:
V>Здравствуйте, busk, Вы писали:
B>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. V>Это невозможно. Доказательство от противного: V>Предположим, что это возможно. V>Тогда существуют два интервала с одинаковым хэшем но разными диапазонами лат. V>Увеличим один из интервалов на один день. V>Его хэш должен остаться тем же (чтобы соблюдалось условие проверки пересечения со вторым интервалом). V>Но вместе с тем, хэш должен измениться, так как появился новый день, который может пересекаться с неким третим интервалом. V>Получаем противоречие, то есть исходная посылка ("Предположим, что это возможно") не верна.
Верно. Но если немножко изменить условие задачи, то хеш таки можно построить — хотя и не факт, что это даст реальный выигрыш для прикладной задачи.
Можно построить такой хеш, что по нему можно определить один из двух исходов — "интервалы точно не пересекаются" и "интервалы возможно пересекаются".
Вообще, любой хеш вводит классы эквивалентности — т.е. вообще нельзя построить хеш (с числом бит меньше, чем у оригинала), из которого можно 100% подтвердить совпадение аргументов.
Всегда выводы делаются из неравенства хешей.
Поэтому нельзя, скажем, написать хеш-функцию для строк так, чтобы сравнивая хеши можно было точно сказать, что строки равны.
Если посмотреть на задачу под этим углом, то решение, в общем-то, тривиально — уменьшаем количество бит на дату, загрубляя точность представления интервалов.
Например, можно оставить только год+месяц, впихнув их в 16 бит. Это уже позволит нам по паре 32-битных хешей определить, что вторая мировая не пересекается с первой мировой.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, vmpire, Вы писали:
V>Здравствуйте, busk, Вы писали:
B>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. V>Предположим, что это возможно. V>Тогда существуют два интервала с одинаковым хэшем но разными диапазонами лат.
Тут приводится доказательство в предположении, что хеши можно сравнивать только на точное равенство. Но в исходном сообщении нет такого ограничения. Действие "сравнить два хеша" не означает же, что возможны только два варианты ответа: "равны" и "различны". Например, есть ещё варианты "больше", "меньше на 52", "отличаются в третьем бите", "взаимно просты", и так далее.
И на практике есть куча алгоритмов, где хеши сравниваются не только на точное совпадение. Например, вся область LSH так устроена.
И решить исходную задачу при этом возможно, и даже точно.
V>Вообще, с практической точки зрения хэш тут совершенно не нужен. Два сравнения по индексу по производительности и так будут будут летать.
Здравствуйте, Sinclair, Вы писали:
B>>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. V>>Это невозможно. Доказательство от противного: S>Верно. Но если немножко изменить условие задачи, то хеш таки можно построить
Тогда это будет уже другая задача, с другим решением.
S>Можно построить такой хеш, что по нему можно определить один из двух исходов — "интервалы точно не пересекаются" и "интервалы возможно пересекаются".
... S>Если посмотреть на задачу под этим углом, то решение, в общем-то, тривиально — уменьшаем количество бит на дату, загрубляя точность представления интервалов. S>Например, можно оставить только год+месяц, впихнув их в 16 бит. Это уже позволит нам по паре 32-битных хешей определить, что вторая мировая не пересекается с первой мировой.
При таком подходе в качестве хеша можно просто брать первую дату интервала.
Если такие хеши равны — интервалы точно пересекаются.
Математически — работает. Практической пользы не имеет.
Если только по условию задачи большинство интервалов не начинается в одну дату.
Здравствуйте, watchmaker, Вы писали:
B>>>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются. V>>Предположим, что это возможно. V>>Тогда существуют два интервала с одинаковым хэшем но разными диапазонами лат.
W>Тут приводится доказательство в предположении, что хеши можно сравнивать только на точное равенство. Но в исходном сообщении нет такого ограничения. Действие "сравнить два хеша" не означает же, что возможны только два варианты ответа: "равны" и "различны". Например, есть ещё варианты "больше", "меньше на 52", "отличаются в третьем бите", "взаимно просты", и так далее.
Сравнение на неравенство тут отпадает из соображений симметрии операции пересечения.
W>И на практике есть куча алгоритмов, где хеши сравниваются не только на точное совпадение. Например, вся область LSH так устроена.
И какая польза в данной задаче от информации "хеши приблизительно равны"? В LSH совсем другая задача решается.
W>И решить исходную задачу при этом возможно, и даже точно.
Покажете решение?
B>Есть интервал в виде дат — два поля. Надо сделать что то типа хэша для данного диапазона чтобы потом можно было сравнивая два хэша сказать, что они пересекаются.
Нет проблем. Надо примерно равномерный хэш для диапазона дат. Можно как-то так сделать (предполагается что в диапазоне конечная дата не включается т.е [h,t) )
#include <stdio.h>
typedef unsigned long long uint64;
int encodeDate(int Year,int Month,int Day) {
int c,ya;
if (Month > 2) Month-=3; else { Month+=9;Year--; }
c =Year/100;
ya=Year-100*c;
c =(146097*c)/4 + (1461*ya)/4 + (153*Month+2)/5 + Day + 1721119;
return c;
}
void decodeDate(int date,int &Year,int &Month,int &Day) {
date -= 1721119;
Year = (4*date-1)/146097;
Day = (4*date-1-146097*Year)/4;
date = (4*Day+3)/1461;
Day = (4*Day+7-1461*date)/4;
Month = (5*Day-3)/153;
Day = (5*Day+2-153*Month)/5;
Year = 100*Year + date;
if (Month < 10) Month+=3; else { Month-=9;Year++; }
}
uint64 pack(int h,int t) { return ((uint64)h<<32)|t; }
void unpack(uint64 v,int &h,int &t) { h=v>>32; t=v; }
uint64 enc(uint64 x) { return x*0x5DE942361AD6BFCBULL; } // замешиваем, можно разными способами
uint64 dec(uint64 x) { return x*0x6ACB5A03516FEDE3ULL; } // востанавливаем
uint64 hashDateRange(int y1,int m1,int d1, int y2,int m2,int d2) {
return enc(pack( encodeDate(y1,m1,d1), encodeDate(y2,m2,d2) ));
}
int isIntersect(uint64 c1,uint64 c2) {
int h1,h2,t1,t2;
unpack(dec(c1),h1,t1);
unpack(dec(c2),h2,t2);
if (h2>h1) h1=h2;
if (t2<t1) t1=t2;
return h1<t1;
}
int main(int argc,char** argv) {
uint64 hash1,hash2; int i1;
hash1=hashDateRange(2010,1,1, 2012,2,1);
hash2=hashDateRange(2011,1,1, 2011,1,2);
i1=isIntersect(hash1,hash2);
printf("hash1=%016llX hash2=%016llX intersect=%d\n",hash1,hash2,i1);
return 0;
}
Здравствуйте, vmpire, Вы писали:
V>В LSH совсем другая задача решается.
Конечно, но это отличный пример того, что работа с хешами совсем не ограничивается тупым сравнением на равенство.
W>>И решить исходную задачу при этом возможно, и даже точно. V>Покажете решение?
Функция хеширования: http://rsdn.org/forum/alg/6727520.1
Правда взяв при этом зачем-то более сложный способ хеширование по сравнению с тривиальным. Но если так требует чувство прекрасного, то почему бы и нет? :)
Здравствуйте, watchmaker, Вы писали:
V>>В LSH совсем другая задача решается. W>Конечно, но это отличный пример того, что работа с хешами совсем не ограничивается тупым сравнением на равенство.
W>>>И решить исходную задачу при этом возможно, и даже точно. V>>Покажете решение? W>Функция хеширования: http://rsdn.org/forum/alg/6727520.1
Правда взяв при этом зачем-то более сложный способ хеширование по сравнению с тривиальным. Но если так требует чувство прекрасного, то почему бы и нет?
Ну так это не хеширование Это упаковка двух дат в один long и распаковка при сравнении.
Количество различных хешей равно количеству различных пар.
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Sinclair, Вы писали:
S>>Допустим, нам известны диапазоны d1 и d2, а также их хеши h1 и h2. S>>Покажите код функции, которая определяет, пересекаются ли диапазоны: S>>
S>>public static boolean AreIntersecting(DateRange d1, DateRange d2, int h1, int h2)
S>>{
S>> if(SomeFunction(h1, h2))
S>> { /// вот тут мы типа ускоряем проверку благодаря использованию хешей
S>> return ???
S>> } else// идём по "медленной" ветке
S>> return (d1.Start <= d2.End) && (d1.End >= d2.Start)
S>>}
S>>
S> Нам нужен 1 дата. Как правило идут набор дат d1, d2, d3, ... dn
Вы решаете какую-то не ту задачу. Обычно под диапазоном понимают интервал, т.е. пара дат — начало и конец.
Но даже если принять ваше понимание задачи — покажите, как предложенная вами хеш-функция её решает. Рассказывать про бинарный поиск не надо — покажите, как использовать ваш хеш.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
S>> Нам нужен 1 дата. Как правило идут набор дат d1, d2, d3, ... dn S>Вы решаете какую-то не ту задачу. Обычно под диапазоном понимают интервал, т.е. пара дат — начало и конец.
А диапозоны могут пересекаться или как интерпретировать дату не попавшую ни в один диапазон, если между ними дырки? S>Но даже если принять ваше понимание задачи — покажите, как предложенная вами хеш-функция её решает. Рассказывать про бинарный поиск не надо — покажите, как использовать ваш хеш.
Был вопрос как сделать хэш по двум датам.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, vmpire, Вы писали:
V>Здравствуйте, watchmaker, Вы писали:
V>>>В LSH совсем другая задача решается. W>>Конечно, но это отличный пример того, что работа с хешами совсем не ограничивается тупым сравнением на равенство.
W>>>>И решить исходную задачу при этом возможно, и даже точно. V>>>Покажете решение? W>>Функция хеширования: http://rsdn.org/forum/alg/6727520.1
Правда взяв при этом зачем-то более сложный способ хеширование по сравнению с тривиальным. Но если так требует чувство прекрасного, то почему бы и нет? V>Ну так это не хеширование Это упаковка двух дат в один long и распаковка при сравнении. V>Количество различных хешей равно количеству различных пар.
Идеальной хеш-функцией называется такая функция, которая отображает каждый ключ из набора S во множество целых чисел без коллизий. В математике такое преобразование называется инъективным отображением.
