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

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

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

Мой алгоритм - решение. Хотя я считаю, что это у такого решения есть серьёзные проблемы с производительностью.
...
Рейтинг: 0 / 0
03.12.2013, 18:32
| Ответить | Цитировать | Написать  
Интервал дат
    #38488019
Мужик
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Мужик
Участник
А в чем принципиальность преобразовывать в значения? В скаляр что ли обязательно нужно?
Можно просто отсортировать по началу интервала и пробежаться по порядку, посмотреть, есть ли пересечения соседних интервалов. В худшем случае O(n * lg n) сложность будет.
...
Рейтинг: 0 / 0
03.12.2013, 20:40
| Ответить | Цитировать | Написать  
Интервал дат
    #38488038
Nordall
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nordall
Гость
Мужик,
Сейчас так и работает, но нужно переделать на скаляр.
...
Рейтинг: 0 / 0
03.12.2013, 21:14
| Ответить | Цитировать | Написать  
Интервал дат
    #38488045
Nordall
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Nordall
Гость
Akina,
Тем не менее это вариант решения.
Если бы оно меня устраивало, вопросов бы на форуме не задавал.
...
Рейтинг: 0 / 0
03.12.2013, 21:19
| Ответить | Цитировать | Написать  
Интервал дат
    #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
03.12.2013, 23:44
| Ответить | Цитировать | Написать  
Интервал дат
    #38488186
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
PS. Формально любой Geometry тип может считаться скаляром, ибо может быть обратимо конвертирован в строку.
...
Рейтинг: 0 / 0
04.12.2013, 00:05
| Ответить | Цитировать | Написать  
Интервал дат
    #38488187
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
Nordall,

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


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