Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / C++ Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Это та-же биткарта. Но я принципиально не хочу решать задачу в SQL так-же как я и решал бы ее на сях.
16 мар 15, 14:21    [17389699]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Получил несолько ложных срабатываний. Разобрался. Забыл что отрезки сами с собой пересекаются.
Убрал само-соединение. Пока пишу... в процессе.
select 
    count(*) 
from 
    geoipcity g1,geoipcity g2
where
  ..... // здесь будет несколько предикатов которые проверяют различные варианты 
  // перекрытия отрезков N_STARTIP1...N_ENDID1, N_STARTIP2...N_ENDID2
  and g1.ROWID!=g2.ROWID;
16 мар 15, 14:35    [17389789]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Задача не заточена под SQL, подобные проблемы обычно биткартой решают. Например в задачах с диапазонами дат используют вспомогательную таблицу-календарь со всеми датами.

Пробуй:
create table #t(id int, n_startip  int, n_endip int)
-- изучаемый
insert into #t values (1, 10, 20) 
-- без перекрытия
insert into #t values (2, 30, 40)
-- перекрытие слева
insert into #t values (3, 5, 15)
-- перекрытие справа
insert into #t values (4, 15, 25)
-- перекрытие сверху
insert into #t values (5, 5, 25)
-- перекрытие снизу
insert into #t values (6, 12, 18)

select A.id, B.id 
	from #t A, #t B
	where A.id != B.id and ((A.n_startip <= B.n_startip and A.n_endip >= B.n_startip and A.n_endip <= B.n_endip) or (A.n_startip <= B.n_startip and A.n_endip >= B.n_endip))
	order by A.id, B.id


drop table #t


Возможно 4 вида перекрытия отрезков: справа, слева, сверху и снизу. При сравнении всем со всеми можно упростить до проверки только слева и сверху, т.к.:
A слева перекрывает B == B справа перекрывает A
A сверху перекрывает B == B снизу перекрывает A

заодно дубли уберутся.

Будут ли использоваться индексы и какие не знаю. Сделай два: (n_startip, n_endip) и (n_endip, n_startip), СУБД сама разберется нужны они или не очень.
16 мар 15, 14:44    [17389864]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Чуть упростил:
select A.id, B.id 
	from #t A, #t B
	where A.id != B.id and A.n_startip <= B.n_startip and (A.n_endip >= B.n_startip and A.n_endip <= B.n_endip or A.n_endip >= B.n_endip)
	order by A.id, B.id
16 мар 15, 15:00    [17389964]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Я надеялся двумя предикатами обойтись. Тоже сидел грыз гранит предикатов max/min и сравнений.

Пока плюнул. Работа подвалила. Вечером вернусь к географии.
16 мар 15, 15:08    [17390007]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2653
Этот код по-моему должен работать, но работает некорректно

		fscanf(in, "%[^,]  , %[^,], \"%[^\"]\", \"%[^\"]\", [^\"]\", \"%[^\"]\", %[^,]   , %[^,]    , %[^,]  ,  %[^\n]", 
			       startIP , endIP,   country ,   region  ,    city  , postalCode, latitude, longitude, dmaCode, areaCode);


Может быть я неправильно его использую в своём контексте, попробуйте у себя
17 мар 15, 02:27    [17392369]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Dima T
Первая корявая получилась. Хотел допилить кавычки и в свою библиотеку прибрать, пригодится, потом подумал обычно надо еще знать сколько всего колонок прежде чем парсить. Получилось проще новую написать :)

Твой файлик проходит без ошибок.

Спс. Закоммитил. С небольшими изменениями. Будет как базовый алгоритм.
https://sourceforge.net/p/countryipdiagram/code/HEAD/tree/trunk/src/ipv4filter.c
17 мар 15, 10:34    [17393302]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Dima T
Чуть упростил:
select A.id, B.id 
	from #t A, #t B
	where A.id != B.id and A.n_startip <= B.n_startip and (A.n_endip >= B.n_startip and A.n_endip <= B.n_endip or A.n_endip >= B.n_endip)
	order by A.id, B.id

Попробуй нагенерить 5 млн случайных строк. Потому как я на Оракле не могу дождаться завершения
работы этого курсора.

Здесь не проблема его написать. А проблема написать оптимально.
17 мар 15, 13:04    [17394261]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
SashaMercury
Этот код по-моему должен работать, но работает некорректно

		fscanf(in, "%[^,]  , %[^,], \"%[^\"]\", \"%[^\"]\", [^\"]\", \"%[^\"]\", %[^,]   , %[^,]    , %[^,]  ,  %[^\n]", 
			       startIP , endIP,   country ,   region  ,    city  , postalCode, latitude, longitude, dmaCode, areaCode);


Может быть я неправильно его использую в своём контексте, попробуйте у себя

Посмотрю чуть позже.
17 мар 15, 13:27    [17394419]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
mayton
Попробуй нагенерить 5 млн случайных строк.

ИМХУ нездоровый тест. Индексы не только сортировка, но и распределение. А также результат: если у тебя пересечений не ожидается, то будет мало, а в рандоме может 100 тыс. пересечься друг с другом и будет 100`000 * 100`000 / 2 = 5`000`000`000 записей ответа.

mayton
Потому как я на Оракле не могу дождаться завершения работы этого курсора.

Ты индексы создал?

Я выше писал: Сделай два: (n_startip, n_endip) и (n_endip, n_startip), СУБД сама разберется нужны они или не очень. Затем план выполнения запроса смотри, там будет сразу видно использует индексы или нет. Как в оракле смотреть не знаю.

Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как.
17 мар 15, 13:56    [17394583]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Dima T
Ты индексы создал?

Чел я же не просто так скрипты привёл. 17382368 Они реальны и работают. По поводу плана исполнения - отпишу чуть позже.
Я не привык писать с бухты-барахты и обычно проверяю.

Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как.

Ты не поверишь но я над этим думаю. Скорее всего эта БД весьма специфична по сути.
Например движок MaxMind и Java-имплементация базы (втроенная) занимала размер
многократ меньше чем CSV-файл.

Для таких данных обычно юзают префиксное дерево или дерево остатков. Вполне возможно
что оно там и заюзано.
17 мар 15, 14:48    [17394894]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Dima T
Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как.

Придумал: хранить в двоичном текстовом виде выравненном до 32 c обрезанными конечными ноликами. Формула обрезки: (n_endip - n_startip), проверяем на вид 0000011111 (т.е. сначала нули, затем единицы) или тоже самое на соответствие (2^n - 1), n - сколько младших бит обрезать от n_startip.

Пример на 4 битах
НачалоКонецХраним
070
4701
45010
81110
121511

дальше сортируем по храним как строки и сравниваем предыдущую с последующей в количестве символов первой - совпало - вторая входит в первую, т.е. "0" == "01" (выкидываем "01"), затем "0" == "010" (выкидываем "010"), затем "0" != "10", затем "10" != "11"

Одна сортировка, один проход, без биткарты, но опять не заточено под SQL
17 мар 15, 15:03    [17395000]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Сделай проверку на валидность:
select ... where (n_endip - n_startip) not in (1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535)

Дальше подзабыл, если больше 65535 будет то это ряд (2^n - 1)
17 мар 15, 15:12    [17395047]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Dima T
Сделай проверку на валидность:

можешь не делать, 10% твоего файла не проходит

mayton
Dima T
Ты индексы создал?

Чел я же не просто так скрипты привёл. 17382368 Они реальны и работают. По поводу плана исполнения - отпишу чуть позже.
Я не привык писать с бухты-барахты и обычно проверяю.

Залил твой файлик в MSSQL. Мой запрос без индексов 10 сек, с индексами 16 сек
17 мар 15, 16:20    [17395495]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Придумал!

Выстроить цепочку:
n_prev_startip = 0
n_prev_endip = 0
1. Взять запись с минимальным n_startip больше n_prev_startip
2. Если n_startip < n_prev_endip значит наложение
3. n_prev_endip = n_endip, n_prev_startip = n_startip
4. если не все пройдены перейти к пункту 1.

Имеем 5 млн. поисков макс. по 24 шага каждый, т.е. ~100 млн операций.
+ код на фоксе
clear
set talk off
set Near On
if !used('tip')
	do create_data
	index on n_startip tag n_startip
endif

n_prev_startip = -1
n_prev_endip = -1
lnSec = seconds()
do while .T.
	seek n_prev_startip
	if eof('tip')
		exit
	endif
	if tip.n_startip < n_prev_endip
		? 'error at line %d', tip.id
	endif
	n_prev_startip = tip.n_startip + 1
	n_prev_endip = tip.n_endip + 1
enddo
? 'time: ', seconds() - lnSec 
return

func create_data
create cursor tip (id i, n_startip n(10), n_endip n(10))
insert into tip values (2, 16777216, 17301503)
insert into tip values (3, 17367040, 17432575)
insert into tip values (4, 17435136, 17435391)
...

Твои 10 тыс проверились за 20 мс :)
17 мар 15, 17:16    [17395797]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Dima T, минутку. Я всё-тки проверю свои 5 млн.

Подожди.

P.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся.
Интересовало портирование этого алгоритма в другие DBMS.
17 мар 15, 19:15    [17396342]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Капец. План вообще никчорту!

SQL> explain plan for select count(*)
  2  from geoipcity where (n_endip - n_startip) not in (
  3  1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535,
  4  power(2,17)-1,
  5  power(2,18)-1,
  6  power(2,17)-1,
  7  power(2,19)-1,
  8  power(2,20)-1,
  9  power(2,21)-1,
 10  power(2,22)-1,
 11  power(2,23)-1,
 12  power(2,24)-1,
 13  power(2,25)-1,
 14  power(2,26)-1,
 15  power(2,27)-1,
 16  power(2,28)-1,
 17  power(2,29)-1,
 18  power(2,30)-1,
 19  power(2,31)-1,
 20  power(2,32)-1,
 21  power(2,17)-1,
 22  power(2,18)-1,
 23  power(2,17)-1,
 24  power(2,19)-1,
 25  power(2,20)-1,
 26  power(2,21)-1,
 27  power(2,22)-1,
 28  power(2,23)-1,
 29  power(2,24)-1);

Explained.

SQL> @?/rdbms/admin/utlxpls;

PLAN_TABLE_OUTPUT
-----------------------------------------------------------------------------------------

Plan hash value: 2075995129

----------------------------------------------------------------------------------
| Id  | Operation             | Name     | Rows  | Bytes | Cost (%CPU)| Time     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT      |          |     1 |    14 | 13738   (8)| 00:02:45 |
|   1 |  SORT AGGREGATE       |          |     1 |    14 |            |          |
|*  2 |   INDEX FAST FULL SCAN| PK_GEOIP |     1 |    14 | 13738   (8)| 00:02:45 |
----------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter("N_ENDIP"-"N_STARTIP"<>1 AND "N_ENDIP"-"N_STARTIP"<>3 AND
              "N_ENDIP"-"N_STARTIP"<>7 AND "N_ENDIP"-"N_STARTIP"<>15 AND
              "N_ENDIP"-"N_STARTIP"<>31 AND "N_ENDIP"-"N_STARTIP"<>63 AND
              "N_ENDIP"-"N_STARTIP"<>127 AND "N_ENDIP"-"N_STARTIP"<>255 AND
              "N_ENDIP"-"N_STARTIP"<>511 AND "N_ENDIP"-"N_STARTIP"<>1023 AND
              "N_ENDIP"-"N_STARTIP"<>2047 AND "N_ENDIP"-"N_STARTIP"<>4095 AND
              "N_ENDIP"-"N_STARTIP"<>8191 AND "N_ENDIP"-"N_STARTIP"<>16383 AND
              "N_ENDIP"-"N_STARTIP"<>32767 AND "N_ENDIP"-"N_STARTIP"<>65535 AND
              "N_ENDIP"-"N_STARTIP"<>131071 AND "N_ENDIP"-"N_STARTIP"<>262143 AND
              "N_ENDIP"-"N_STARTIP"<>524287 AND "N_ENDIP"-"N_STARTIP"<>1048575 AND
              "N_ENDIP"-"N_STARTIP"<>2097151 AND "N_ENDIP"-"N_STARTIP"<>4194303 AND
              "N_ENDIP"-"N_STARTIP"<>8388607 AND "N_ENDIP"-"N_STARTIP"<>16777215 AND
              "N_ENDIP"-"N_STARTIP"<>33554431 AND "N_ENDIP"-"N_STARTIP"<>67108863 AND
              "N_ENDIP"-"N_STARTIP"<>134217727 AND "N_ENDIP"-"N_STARTIP"<>268435455 AND
              "N_ENDIP"-"N_STARTIP"<>536870911 AND "N_ENDIP"-"N_STARTIP"<>1073741823
              AND "N_ENDIP"-"N_STARTIP"<>2147483647 AND
              "N_ENDIP"-"N_STARTIP"<>4294967295)

Какого осьминога ему тут нужен PRIMARY key???
17 мар 15, 19:34    [17396420]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
alter index ... invisible помог. Хорошая шняга в одинадцатом жигуле Оракле... Мдя.
17 мар 15, 19:40    [17396437]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
--------------------------------------------------------------------------------
| Id  | Operation          | Name      | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |           |     1 |    14 | 16854   (7)| 00:03:23 |
|   1 |  SORT AGGREGATE    |           |     1 |    14 |            |          |
|*  2 |   TABLE ACCESS FULL| GEOIPCITY |     1 |    14 | 16854   (7)| 00:03:23 |
--------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - filter("N_ENDIP"-"N_STARTIP"<>1 AND "N_ENDIP"-"N_STARTIP"<>3 AND............
17 мар 15, 19:42    [17396444]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Два мильйона. Это примерно половина всей базы .
  COUNT(*)
----------
   2069549
17 мар 15, 19:58    [17396498]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
mayton
P.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся.
Интересовало портирование этого алгоритма в другие DBMS.

rushmore
В данном случае можно ассоциативным массивом обойтись. arr[start_ip] = end_ip. Например <map> в С++

В SQL он не впишется, т.к. противоречит концепции реляционных БД. Через одно место можно попробовать впихнуть, но оно и будет работать соответственно.
17 мар 15, 20:01    [17396515]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
mayton
Два мильйона. Это примерно половина всей базы .
  COUNT(*)
----------
   2069549

Забей на проверку масок, идея не взлетела, я же проверил на твоем файлике, выше писал.
17 мар 15, 20:03    [17396519]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
Dima T
Member

Откуда:
Сообщений: 15689
Я замудрено придумал, проще так:
сортируем по n_startip
идем последовательно
если текущий n_startip < предыдущий n_endip значит перекрытие

Одна сортировка, один проход. Лучше не будет.

это с небольшими извратами можно даже в оракле/мсскул селектом выбрать.
17 мар 15, 20:12    [17396558]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Dima T, +1.

Это будет констрейнтом в работе самого приложения. Во врема парсинга будет просто
происходить проверка двух соседник строк на перекрытие диапазонов.

Так и сделаем.

А самую первую (изначальную) сортировку по beginIp можно сделать в оффлайне и пересохранить исходный файл.
17 мар 15, 20:20    [17396593]     Ответить | Цитировать Сообщить модератору
 Re: Тяпничная география  [new]
mayton
Member

Откуда: loopback
Сообщений: 51019
Хм... самопальный IP2num не взлетает.

// This is stuped IPv4 to number converter. Is it works? I.d.n.t. know! Mua-haha... Did n't tested.
uint32_t ipv4toNum(char *IPv4){
	uint32_t ipInt = 0;	
	char *p = (char*)strtok(IPv4,".");
	ipInt |= (atoi(p));
	p = (char*)strtok(NULL,".");
	ipInt |= (atoi(p) << 8);
	p = (char*)strtok(NULL,".");
	ipInt |= (atoi(p) << 16);
	p = (char*)strtok(NULL,".");
	ipInt |= (atoi(p) << 24);
	return ipInt;
}
.....
			printf("startIpNum = '%s'\n", val[0]);
			printf("endIpNum   = '%s'\n", val[1]);
			printf("country    = '%s'\n", val[2]);
			printf("region     = '%s'\n", val[3]);
			printf("city       = '%s'\n", val[4]);
			printf("postalCode = '%s'\n", val[5]);
			printf("latitude   = '%s'\n", val[6]);
			printf("longitude  = '%s'\n", val[7]);
			printf("dmaCode    = '%s'\n", val[8]);
			printf("areaCode   = '%s'\n", val[9]);
			printf("n_startip  = %d\n", ipv4toNum(val[0]));
			printf("n_endip    = %d\n", ipv4toNum(val[1]));

Чортовы сишные сдвиги. Наверное где-то разрядная сетка рубится.

startIpNum = '1.0.0.0'
endIpNum   = '1.7.255.255'
country    = 'AU'
region     = ''
city       = ''
postalCode = ''
latitude   = '-27.0000'
longitude  = '133.0000'
dmaCode    = ''
areaCode   = ''
n_startip  = 1
n_endip    = -63743
---------------------
startIpNum = '1.9.0.0'
endIpNum   = '1.9.255.255'
country    = 'MY'
region     = ''
city       = ''
postalCode = ''
latitude   = '2.5000'
longitude  = '112.5000'
dmaCode    = ''
areaCode   = ''
n_startip  = 2305
n_endip    = -63231
18 мар 15, 00:43    [17397165]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 [5] 6 7 8   вперед  Ctrl      все
Все форумы / C++ Ответить