powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная география
25 сообщений из 177, страница 5 из 8
Тяпничная география
    #38905926
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это та-же биткарта. Но я принципиально не хочу решать задачу в SQL так-же как я и решал бы ее на сях.
...
Рейтинг: 0 / 0
Тяпничная география
    #38905938
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Получил несолько ложных срабатываний. Разобрался. Забыл что отрезки сами с собой пересекаются.
Убрал само-соединение. Пока пишу... в процессе.
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
select 
    count(*) 
from 
    geoipcity g1,geoipcity g2
where
  ..... // здесь будет несколько предикатов которые проверяют различные варианты 
  // перекрытия отрезков N_STARTIP1...N_ENDID1, N_STARTIP2...N_ENDID2
  and g1.ROWID!=g2.ROWID;
...
Рейтинг: 0 / 0
Тяпничная география
    #38905950
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Задача не заточена под SQL, подобные проблемы обычно биткартой решают. Например в задачах с диапазонами дат используют вспомогательную таблицу-календарь со всеми датами.

Пробуй:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
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), СУБД сама разберется нужны они или не очень.
...
Рейтинг: 0 / 0
Тяпничная география
    #38905966
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Чуть упростил:
Код: plaintext
1.
2.
3.
4.
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
...
Рейтинг: 0 / 0
Тяпничная география
    #38905981
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я надеялся двумя предикатами обойтись. Тоже сидел грыз гранит предикатов max/min и сравнений.

Пока плюнул. Работа подвалила. Вечером вернусь к географии.
...
Рейтинг: 0 / 0
Тяпничная география
    #38906528
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Этот код по-моему должен работать, но работает некорректно

Код: plaintext
1.
2.
		fscanf(in, "%[^,]  , %[^,], \"%[^\"]\", \"%[^\"]\", [^\"]\", \"%[^\"]\", %[^,]   , %[^,]    , %[^,]  ,  %[^\n]", 
			       startIP , endIP,   country ,   region  ,    city  , postalCode, latitude, longitude, dmaCode, areaCode);



Может быть я неправильно его использую в своём контексте, попробуйте у себя
...
Рейтинг: 0 / 0
Тяпничная география
    #38906730
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TПервая корявая получилась. Хотел допилить кавычки и в свою библиотеку прибрать, пригодится, потом подумал обычно надо еще знать сколько всего колонок прежде чем парсить. Получилось проще новую написать :)

Твой файлик проходит без ошибок.
Спс. Закоммитил. С небольшими изменениями. Будет как базовый алгоритм.
https://sourceforge.net/p/countryipdiagram/code/HEAD/tree/trunk/src/ipv4filter.c
...
Рейтинг: 0 / 0
Тяпничная география
    #38906984
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TЧуть упростил:
Код: plaintext
1.
2.
3.
4.
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 млн случайных строк. Потому как я на Оракле не могу дождаться завершения
работы этого курсора.

Здесь не проблема его написать. А проблема написать оптимально.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907026
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЭтот код по-моему должен работать, но работает некорректно

Код: plaintext
1.
2.
		fscanf(in, "%[^,]  , %[^,], \"%[^\"]\", \"%[^\"]\", [^\"]\", \"%[^\"]\", %[^,]   , %[^,]    , %[^,]  ,  %[^\n]", 
			       startIP , endIP,   country ,   region  ,    city  , postalCode, latitude, longitude, dmaCode, areaCode);



Может быть я неправильно его использую в своём контексте, попробуйте у себя
Посмотрю чуть позже.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907080
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907175
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TТы индексы создал?

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

Кстати есть еще одна особенность диапазонов IP: они всегда отвечают условию: начало (т.е. n_startip) сформировано в двоичном виде как число с 8/16/24 ноликами в конце ( ...1000000000), максимальное (n_endip) в конце 8/16/24 единиц. Надо проверить что у как-то эту особенность использовать. Пока не соображу как.
Ты не поверишь но я над этим думаю. Скорее всего эта БД весьма специфична по сути.
Например движок MaxMind и Java-имплементация базы (втроенная) занимала размер
многократ меньше чем CSV-файл.

Для таких данных обычно юзают префиксное дерево или дерево остатков. Вполне возможно
что оно там и заюзано.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907201
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 битах
НачалоКонецХраним07047014501081110121511
дальше сортируем по храним как строки и сравниваем предыдущую с последующей в количестве символов первой - совпало - вторая входит в первую, т.е. "0" == "01" (выкидываем "01"), затем "0" == "010" (выкидываем "010"), затем "0" != "10", затем "10" != "11"

Одна сортировка, один проход, без биткарты, но опять не заточено под SQL
...
Рейтинг: 0 / 0
Тяпничная география
    #38907211
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сделай проверку на валидность:
Код: plaintext
1.
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)
...
Рейтинг: 0 / 0
Тяпничная география
    #38907315
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TСделай проверку на валидность:
можешь не делать, 10% твоего файла не проходит

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

Чел я же не просто так скрипты привёл. 17382368 Они реальны и работают. По поводу плана исполнения - отпишу чуть позже.
Я не привык писать с бухты-барахты и обычно проверяю.
Залил твой файлик в MSSQL. Мой запрос без индексов 10 сек, с индексами 16 сек
...
Рейтинг: 0 / 0
Тяпничная география
    #38907381
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Придумал!

Выстроить цепочку:
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 млн операций.
код на фоксе
Код: 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.
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 мс :)
...
Рейтинг: 0 / 0
Тяпничная география
    #38907499
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, минутку. Я всё-тки проверю свои 5 млн.

Подожди.

P.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся.
Интересовало портирование этого алгоритма в другие DBMS.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907509
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Капец. План вообще никчорту!

Код: plsql
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.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
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???
...
Рейтинг: 0 / 0
Тяпничная география
    #38907513
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alter index ... invisible помог. Хорошая шняга в одинадцатом жигуле Оракле... Мдя.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907516
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: plsql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
--------------------------------------------------------------------------------
| 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............
...
Рейтинг: 0 / 0
Тяпничная география
    #38907523
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Два мильйона. Это примерно половина всей базы .
Код: plsql
1.
2.
3.
  COUNT(*)
----------
   2069549
...
Рейтинг: 0 / 0
Тяпничная география
    #38907525
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonP.S. А я всегда хвалил Фокс-Про. И даже поднимал где-то тему по поводу rushmap или как оно там зовётся.
Интересовало портирование этого алгоритма в другие DBMS.
rushmore
В данном случае можно ассоциативным массивом обойтись. arr[start_ip] = end_ip. Например <map> в С++

В SQL он не впишется, т.к. противоречит концепции реляционных БД. Через одно место можно попробовать впихнуть, но оно и будет работать соответственно.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907527
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДва мильйона. Это примерно половина всей базы .
Код: plsql
1.
2.
3.
  COUNT(*)
----------
   2069549


Забей на проверку масок, идея не взлетела, я же проверил на твоем файлике, выше писал.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907533
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я замудрено придумал, проще так:
сортируем по n_startip
идем последовательно
если текущий n_startip < предыдущий n_endip значит перекрытие

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

это с небольшими извратами можно даже в оракле/мсскул селектом выбрать.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907539
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, +1.

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

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

А самую первую (изначальную) сортировку по beginIp можно сделать в оффлайне и пересохранить исходный файл.
...
Рейтинг: 0 / 0
Тяпничная география
    #38907704
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хм... самопальный IP2num не взлетает.

Код: plaintext
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.
// 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]));


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

Код: php
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.
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
...
Рейтинг: 0 / 0
25 сообщений из 177, страница 5 из 8
Форумы / C++ [игнор отключен] [закрыт для гостей] / Тяпничная география
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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