Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Интервал дат / 16 сообщений из 16, страница 1 из 1
03.12.2013, 15:04
    #38487482
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Добрый день!
В качестве входных данных подается набор из N интервалов дат :
1.dt1,dt2
2.dt3,dt4
3.dt5,dt6
...
Нужно написать функцию, которая будет преобразовывать входные интервалы в значения,
по которым можно было бы определить пересекаются эти интервалы или нет.
Подскажите, пожалуйста, как это можно сделать?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 15:13
    #38487505
wadman
wadman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
NordallПодскажите, пожалуйста, как это можно сделать?
То есть написать решение за тебя?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 15:15
    #38487512
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
wadman,
это было бы простозамечательно.
Указание в каком направлении двигаться было бы более чем достаточно:название алгоритма и т.д.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 15:21
    #38487522
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Nordallпреобразовывать входные интервалы в значения,
по которым можно было бы определить пересекаются эти интервалы или нет.
В такой постановке задача нерешаема. Ты хочешь получить нулевую размерность, но сравнивать на уровне первой, которая в результатах свёртки просто отсутствует.

Если же тебе надо принять ДВА интервала и вернуть, пересекаются они или нет - просто анализируй знак выражения

(начало1 - конец2) * (начало2 - конец1)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 15:52
    #38487601
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Akina,
Спасибо за совет.
У меня решение есть, но с производительностью есть вопросы:
Для каждой интервала возвращаем массив всех дат из него (для первого: dt1,dt1+1,dt1+2,...,dt2) и сохраняем его в буфере.
После обработки последнего интервала проверяем на уникальность дат в буфере.(это самый прямой алгоритм, естественно можно его улучшить)
Если все даты уникальны, значит интервалы не пересекаются.
Проблема в том что интервалы вида '03.12.2013' - '31.12.5999' будут возвращать 2916854 значений.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 15:54
    #38487607
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
очепятка '31.12.5999'->'31.12.9999'
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 18:32
    #38487905
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
NordallУ меня решение есть, но Это - не решение. Это full trЫndetz erotic international...

Мой алгоритм - решение. Хотя я считаю, что это у такого решения есть серьёзные проблемы с производительностью.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 20:40
    #38488019
Мужик
Мужик
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
А в чем принципиальность преобразовывать в значения? В скаляр что ли обязательно нужно?
Можно просто отсортировать по началу интервала и пробежаться по порядку, посмотреть, есть ли пересечения соседних интервалов. В худшем случае O(n * lg n) сложность будет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 21:14
    #38488038
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Мужик,
Сейчас так и работает, но нужно переделать на скаляр.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 21:19
    #38488045
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Akina,
Тем не менее это вариант решения.
Если бы оно меня устраивало, вопросов бы на форуме не задавал.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.12.2013, 23:44
    #38488163
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Вводишь в проект MySQL-сервер. И со свистом обрабатываешь большие массивы данных одним махом:

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
mysql> CREATE TABLE Periods (ID INT AUTO_INCREMENT PRIMARY KEY, dFrom TIMESTAMP, dTo TIMESTAMP);
Query OK, 0 rows affected (0.03 sec)

mysql>
mysql> INSERT INTO Periods (dFrom, dTo)
    -> SELECT '2013-01-01', '2013-01-03'
    -> UNION ALL
    -> SELECT '2013-01-02', '2013-01-04'
    -> UNION ALL
    -> SELECT '2013-01-04', '2013-01-05'
    -> ;
Query OK, 3 rows affected (0.02 sec)
Records: 3  Duplicates: 0  Warnings: 0

mysql>
mysql> SELECT ID, dFrom, dTo FROM Periods;
+----+---------------------+---------------------+
| ID | dFrom               | dTo                 |
+----+---------------------+---------------------+
|  1 | 2013-01-01 00:00:00 | 2013-01-03 00:00:00 |
|  2 | 2013-01-02 00:00:00 | 2013-01-04 00:00:00 |
|  3 | 2013-01-04 00:00:00 | 2013-01-05 00:00:00 |
+----+---------------------+---------------------+
3 rows in set (0.00 sec)

mysql>
mysql> CREATE FUNCTION PeriodsIntersect(From_1 TIMESTAMP, To_1 TIMESTAMP, From_2 TIMESTAMP, To_2 TIMESTAMP)
    -> RETURNS INT(1) DETERMINISTIC
    -> RETURN Intersects(
    -> GeomFromText(CONCAT ('LineString(', UNIX_TIMESTAMP(From_1), ' 0,', UNIX_TIMESTAMP(To_1),' 0)')),
    -> GeomFromText(CONCAT ('LineString(', UNIX_TIMESTAMP(From_2), ' 0,', UNIX_TIMESTAMP(To_2),' 0)'))
    -> );
Query OK, 0 rows affected (0.00 sec)

mysql>
mysql> SELECT t1.dFrom dFrom1, t1.dTo dTo1
    ->      , t2.dFrom dFrom2, t2.dTo dTo2
    ->      , PeriodsIntersect(t1.dFrom, t1.dTo, t2.dFrom, t2.dTo) Intersect
    -> FROM Periods t1, Periods t2
    -> WHERE t1.Id != t2.Id;
+---------------------+---------------------+---------------------+---------------------+-----------+
| dFrom1              | dTo1                | dFrom2              | dTo2                | Intersect |
+---------------------+---------------------+---------------------+---------------------+-----------+
| 2013-01-02 00:00:00 | 2013-01-04 00:00:00 | 2013-01-01 00:00:00 | 2013-01-03 00:00:00 |         1 |
| 2013-01-04 00:00:00 | 2013-01-05 00:00:00 | 2013-01-01 00:00:00 | 2013-01-03 00:00:00 |         0 |
| 2013-01-01 00:00:00 | 2013-01-03 00:00:00 | 2013-01-02 00:00:00 | 2013-01-04 00:00:00 |         1 |
| 2013-01-04 00:00:00 | 2013-01-05 00:00:00 | 2013-01-02 00:00:00 | 2013-01-04 00:00:00 |         1 |
| 2013-01-01 00:00:00 | 2013-01-03 00:00:00 | 2013-01-04 00:00:00 | 2013-01-05 00:00:00 |         0 |
| 2013-01-02 00:00:00 | 2013-01-04 00:00:00 | 2013-01-04 00:00:00 | 2013-01-05 00:00:00 |         1 |
+---------------------+---------------------+---------------------+---------------------+-----------+
6 rows in set (0.00 sec)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.12.2013, 00:05
    #38488186
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
PS. Формально любой Geometry тип может считаться скаляром, ибо может быть обратимо конвертирован в строку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.12.2013, 00:06
    #38488187
Aleksandr Sharahov
Aleksandr Sharahov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Nordall,

вместо двух дат храни один int64 - вот тебе и скаляр
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.12.2013, 12:33
    #38488668
Nordall
Nordall
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
Akina,
спасибо за наиподробнейший пример!
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.12.2013, 12:36
    #38488675
softwarer
softwarer
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
AkinaМой алгоритм - решение. Хотя я считаю, что это у такого решения есть серьёзные проблемы с производительностью.
У него будет нормальная производительность, если интервалы перед сравнением отсортировать по дате начала. И в этом подходе содержится намёк на дальнейшее улучшение производительности :)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.12.2013, 14:56
    #38488971
Akina
Akina
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Интервал дат
softwarerAkinaМой алгоритм - решение. Хотя я считаю, что это у такого решения есть серьёзные проблемы с производительностью.
У него будет нормальная производительность, если интервалы перед сравнением отсортировать по дате начала. И в этом подходе содержится намёк на дальнейшее улучшение производительности :)
Мы до сих пор не в курсе, гда, как, что и почём. Скажем, в случае реализации моего алгоритма в СУБД сортировка нахрен не нужна.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Интервал дат / 16 сообщений из 16, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 737ms
Закрыть
start [/forum/topic.php?fid=16&mobile=1&tid=1341549]:
 0ms
get settings:
 6ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 418ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 51ms
get tp. blocked users:
 1ms
others: 229ms
total:  737ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]