Никакой оптимизации не рассматривается. Индексы не упоминаются
Все сделано "влоб" пока текла мысль только для проверки работы "механизма".
-- пример использования BIT_COUNT() с родными BIT значениями
1.
2.
3.
4.
SELECT BIT_COUNT(b'100111') as BBB;
BBB
---------------------
4
4 единицы-бита.
тип BIT ограничение 64 бита (или было или уже нет - не суть)
хочется писать в одну простую строку 0 1, поэтому буду использовать BINARY, как "близкий" тип к CHAR
в варианте с BINARY
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
SELECT BIT_COUNT(CAST('000000' AS BINARY(6))) as BBB;
BBB
--------------------------------------
12
>SELECT BIT_COUNT(CAST('100111' AS BINARY(6))) as BBB;
BBB
--------------------------------------
16
т.е. в BINARY позиция - 2 бита ("0") и 3 бита ("1")
это все тонкости. Можем использовать тип BINARY в функции BIT_COUNT(), вычитая 2 Х "длину строки", получим кол-во "Единиц"
Дано - наборы чисел (множеств) dano.txt20 строк, во вложении файл 100строк31.05.2007 13 14 15 17 21 26 29 31 32 34 38 39 40 42 44 51 60 63 67 7601.06.2007 2 9 13 14 15 24 27 32 33 41 48 50 52 54 61 62 63 65 67 7302.06.2007 2 4 5 10 15 18 21 31 32 37 39 47 49 52 55 60 63 66 68 7103.06.2007 2 9 12 18 21 25 27 29 36 39 40 46 50 53 56 61 64 68 69 7704.06.2007 2 10 12 17 19 20 26 30 32 40 45 50 55 62 69 70 72 73 77 7905.06.2007 1 3 4 7 18 19 23 27 33 35 38 46 50 55 56 57 60 63 76 7906.06.2007 10 12 24 27 34 37 38 41 46 47 52 53 56 58 59 62 64 66 70 7707.06.2007 1 7 9 10 12 14 16 21 22 26 30 32 34 41 43 47 49 50 65 7908.06.2007 5 6 7 15 17 21 23 25 26 36 41 48 54 55 57 59 65 67 74 7909.06.2007 2 5 8 16 19 22 23 28 35 40 47 48 57 65 66 67 68 70 74 7610.06.2007 14 17 19 21 25 26 29 30 32 33 34 35 42 43 46 56 59 62 74 7611.06.2007 3 7 12 23 31 32 33 41 42 46 50 55 57 60 61 66 69 76 77 7912.06.2007 4 7 9 27 28 30 34 35 37 42 46 50 51 56 57 62 63 68 70 7413.06.2007 1 10 25 27 30 36 39 46 47 52 53 55 56 59 62 66 69 70 73 7414.06.2007 7 14 21 22 26 27 30 32 34 41 49 55 59 63 64 65 72 73 77 7915.06.2007 1 4 12 15 24 25 34 35 36 39 50 51 56 59 61 67 68 73 76 7816.06.2007 2 5 9 12 14 15 16 20 23 26 28 51 52 56 60 61 65 71 75 7717.06.2007 8 13 14 17 18 20 27 29 35 39 40 42 48 49 54 57 59 65 69 7318.06.2007 1 3 5 6 7 18 19 21 28 34 41 45 55 59 64 68 70 73 78 7919.06.2007 3 10 11 21 29 34 37 38 43 46 47 49 50 55 60 61 70 71 73 76
в данном случае предполагаются наборы множеств по 20 чисел, числа до сотни - 1..99
Задача - получить максимальное количество строк, пересекающихся количеством элементов K
таблицы - с данными - daNO, рабочая OTvet
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
DROP TABLE IF EXISTS dano;
CREATE TABLE `dano` (
id int NOT NULL AUTO_INCREMENT,
str10 char(60) DEFAULT NULL,
ddt date DEFAULT NULL,
bin10 binary(100) DEFAULT NULL,
PRIMARY KEY (id)
);
DROP TABLE IF EXISTS otvet;
CREATE TABLE otvet (
id1 int DEFAULT NULL,
id2 int DEFAULT NULL,
strin char(100) DEFAULT NULL,
bin10 binary(100) DEFAULT NULL,
XXX int DEFAULT NULL
);
2 вспомогательные функции
StrToBit - перевод множества чисел в "битовый вид", учитываем что у нас числа из первой сотни 1..99, берем "строку длиной 100 позиций" (99 не по феньшую), но тип не CHAR(100) а BINARY (100) для
"нормальной" работы функции BIT_COUNT() - подсчет БИТ-Единиц
(в строку из 0 и 1, где номер позиции Единицы - это признак наличия числа в множестве ) например [1 5 7] = '1000101' (здесь считаем слева-направо, для удобочитаемости)
BitToStr - обратный перевод '1000101' или '100010100000000' = [1 5 7] (смотрим слева-направо)
функции не претендуют на оптимальность и скорострельность, писалось влет "чтобы работало"
StrToBit и BitToStr
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.
/* Строку из чисел через пробел переводит в строку "бит" 0,1 */
CREATE FUNCTION StrToBit(StrIn char(100))
RETURNS BINARY(100)
DETERMINISTIC
NO SQL
BEGIN
DECLARE b char(100);
DECLARE n, pp int DEFAULT 0;
SET b = REPEAT('0',100);
WHILE LOCATE(" ", StrIn) DO
SET n=LOCATE(" ", StrIn);
SET pp=LEFT(StrIn, n)+0;
set b=INSERT(b,pp,1,'1');
SET StrIn = SUBSTRING(StrIn, n+1);
END WHILE;
SET pp=LEFT(StrIn, n)+0;
set b=INSERT(b,pp,1,'1');
RETURN b;
END
/* --------------- */
/* и биты в строку для визуализации*/
CREATE FUNCTION BitToStr(sss BINARY(100))
RETURNS CHAR(100)
DETERMINISTIC
NO SQL
BEGIN
DECLARE i int DEFAULT 1;
DECLARE ch char(100) DEFAULT '';
WHILE i<=100 DO
IF SUBSTRING(sss,i,1)=1 THEN
SET ch = CONCAT( ch,' ', i);
END IF;
SET i:=i+1;
END WHILE;
SET ch = SUBSTRING(ch,2);
RETURN ch;
END
загрузка данных
1.
2.
3.
LOAD DATA INFILE "D:/dano.txt" INTO TABLE dano
FIELDS TERMINATED BY ', ' (@myddt,str10) set ddt=STR_TO_DATE(@myddt,"%d.%m.%Y");
UPDATE dano d SET d.bin10 = StrToBit(d.str10);
попарное пересечение множеств
(t1.bin10
& t2.bin10 - логическое
И для битовых значений дает пересечение Единиц, пример '01001' & '10111' = '00001'
BIT_COUNT('01001' & '10111') = 1 считает кол-во совпадающих "Единиц" )
находим решение для K=5
пишем эти данные в рабочую таблицу OTvet
1.
2.
3.
4.
5.
6.
7.
8.
9.
INSERT INTO otvet
SELECT t1.id str1, t2.id AS str2,
BitToStr(t1.bin10 & t2.bin10) AS alles,
(t1.bin10 & t2.bin10) AS dgt,
BIT_COUNT(t1.bin10 & t2.bin10)-200 AS XXX -- кол-во чисел в пересечении
-- длина 100, поэтому - 100*2 =200 (для типа Binary(100))
FROM dano t1 JOIN dano t2 ON t1.id < t2.id
HAVING XXX>=5 -- минимально необходимое кол-во чисел в пересечении (совпадении) множеств для минимизации таблицы
;
очень неоптимальный запрос, но визуально максимально понятный
(этот конечный запрос зависит от поставленной задачи)
1.
2.
3.
4.
5.
6.
7.
8.
SELECT GROUP_CONCAT(t.id), t.strin, t.XXX, COUNT(t.strin) AS yyy FROM
(SELECT o.id1 AS id, o.strin, o.XXX FROM otvet o WHERE o.XXX >= 5
UNION
SELECT o.id2 AS id, o.strin, o.XXX FROM otvet o WHERE o.XXX >= 5
) AS t
GROUP BY t.strin, t.XXX
HAVING yyy>=2
ORDER BY yyy DESC;
получаем
строки пересечение
StrIn Кол-во чисел в наборе
K кол-во строк совпадений
yyy 24/30/3 2 10 15 21 32 49 71 7 3100/29/95 7 36 38 48 65 5 324/8 1 10 12 21 22 30 32 41 49 65 10 2
искали вхождение Пятерок K=5
ответом задачи будут записи с макс "кол-во строк " для K>=5
24/30/3 2 10 15 21 32 49 71 7 3100/29/95 7 36 38 48 65 5 3
комбинацию 7 чисел [2 10 15 21 32 49 71] необходимо разложить по 5 (на клиенте)
хотелось уйти от комбинаторики, но в конце она нас настигла, но уже не в том объеме
--PS
мысль изыди!
