[closed]Вставка 1 000 000 уникальных случайных значений

Question

[Михаил]

Необходимо вставить в базу 1 000 000 уникальных сгенерированных слов длинной в 4 символа.Алфавит русский. Язык реализации — php. Я сделал при помощи In_array, но скорость обработки меня не порадовала. Помогите пожалуйста с идеей?

upd: решение найдено

Comments

[Сергей Наломенко]

Слова нужно генерировать самому? Или есть входные данные?

[Михаил]

задается кол-во букв. дальше нужно составить множество уникальных значений

Answer 1

[Михаил]

решил вопрос созданием дополнительной таблицы, дальше используется способ с UNIQUE KEY. После эксперимента дополнительная таблица полностью чистится. Всем спасибо:)

Comments

[Сергей Наломенко]

Поставьте метку «решение» на свой ответ, так понятнее будет смотреься решенная задача в ленте Q&A :)

Answer 2

[xaker1]

как вариант — все слова кидаете в массив, но в качестве ключей. Подсчитываете количество элементов в массиве — и добавляете n недостающих слов — опять проверяете. И так, пока количество элементов не будет = 1000000.
Потом все ключи кидаете в базу.
Не знаю, насколько будет быстрее, но это первое что пришло в голову)

Comments

[Михаил]

как вариант — все слова кидаете в массив, но в качестве ключей. уже на 400 000 вылетает по памяти — больше 134мб оперативы лимит :(

[xaker1]

Увеличивайте лимит)
Странно, что на обычных массивах не вылетает

[Михаил]

может из за русского алфавита? я что то не подумал. Нужно хеш их собрать и сравнивать по хешу

[xaker1]

Кстати, тоже вариант. Сразу пишем в базу — а храним только хэш. Хотя… сомневаюсь в оправданности такого подхода. Не будет ли хэш занимать в памяти больше места, чем оригинальная строка?

Answer 3

[p4s8x]

Можно просто сгенерировать 1 000 000 уникальных чисел(10тичной системы счисления), а затем перевести результат в четверичную систему счисления, и заменить {0,1,2,3} на свой алвафит.

Сгенерировать можно используя базу: что-то вроде
while ($n<1000000)
{
if(mysql_query("INSERT INTO keys (value) VALUES ("
. rand_val() . ")")))
{
$n++;
}

}

а у таблицы прописать UNIQUE KEY `value` (`uniq_value`)

Comments

[Михаил]

слово должно быть в четыре символа длинной*

[p4s8x]

Тогда
function rand_val()
{
$str="abcdefghijklmnop123465";
return substr(str_shuffle($str),0,4)
}

[Михаил]

>а у таблицы прописать UNIQUE KEY `value` (`uniq_value`)
никак не прописать :(

[p4s8x]

Почему никак не прописать?
ALTER TABLE table1 ADD UNIQUE (value)?

Answer 4

[nikitasius]

попробуйте алгоритм ru.wikipedia.org/wiki/Mersenne_twister

Comments

[p4s8x]

PHP функция mt_rand поэтому и называется Mt )

[message]

и работает в 4 раза быстрее простого rand

Answer 5

[Ryuzaki]

Если я всё правильно понял, то можно сгенерировать все возможные значения, записать их в массив, сделать shuffle и взять только первый миллион.

<?
$words=array();
$w='aaaa';
for($i1=0;$i1<27;$i1++)
for($i2=0;$i2<27;$i2++)
for($i3=0;$i3<27;$i3++)
for($i3=0;$i3<27;$i3++)
{
$w[0]=chr(97+$i1);
$w[1]=chr(97+$i2);
$w[2]=chr(97+$i3);
$w[3]=chr(97+$i4);
$words[]=$w;
}
shuffle($words);

?>

Comments

[Михаил]

а если поменяются входные данные… не, тут слишком жесто :(

Answer 6

[Сергей Наломенко]

Вот вариант решения рекурсивным перебором по заданному алфавиту. Все параметры задаются (кол-во символов, кол-во слов и, собственно, сам алфавит-набор символов). Только что проверил, работает.

<?
function generate($depth = 0, $str = "")
{
global $ABC, $lettersCount, $c, $wordsCount;

if($depth == $lettersCount)
{
mysql_query("INSERT INTO `table` SET `value`='$str'");

$c++;
return;
}

for($i = 0; $i < strlen($ABC); $i++)
{
generate($depth + 1, $str.$ABC[$i]);
if($c == $wordsCount)
{
echo "Сгенерировано $c слов";
exit;
}
}
}

$ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
$lettersCount = 4; //кол-во символов
$wordsCount = 1000000; //кол-во слов

$c = 0;

generate();
?>


Comments

[Михаил]

но они же не случайны)

[Сергей Наломенко]

А я в условии никакого упоминания про случайность и не видел :) Сказано «уникальные». И тут каждая строка уникальна. Вот, собственно, и всё, разве не так? )

[Сергей Наломенко]

UPD: сейчас увидел слово «случайных». Что-то обновлялось? )

[Михаил]

нет не менялось)

[Сергей Наломенко]

Минус мне за внимательность. Только не в карму ))

Answer 7

[Анатолий]

Как вариант можете сренерить массив с 1000000 ключей с одним значением ""
ключи будут состоять из 4 цифр, если Вам нужно будет значение, просто возьмете chr от значений. поиск значения по ключу будет быстрей чем поиск по значению, причем, мне кажется, на много быстрей + работа с числами будет быстрей чем работа со строками. Строки показывайте лишь по мере необходимости.

Answer 8

[Ivan Komarov]

Если взять только нижний регистр, то получается 33^4 = 1185921
Я бы сгенерировать все варианты, и рандомом поудалял лишние, до 1000000.
А если нужнен и верхний, то прошелся по полученной выборке и тоже рандомом сделал бы преобразование в верхний. И никаких проверок на уникальность не надо.

Но вообще не понятно, зачем вам это писать на php, я бы сделал бы прямо на mysql:

хранимка:
BEGIN
SET @str = 'абвгдежзийклмнопрстуфхцчшщъыьэюя';

SET @a = 1;

WHILE @a < 33 DO
SET @b = 1;
WHILE @b < 33 DO
SET @c = 1;
WHILE @c < 33 DO
SET @d = 1;
WHILE @d < 33 DO
-- тут можно добавить случайное преобразование в верхний регистр
INSERT INTO test (word) VALUES(concat(
substr(@str, @a, 1),
substr(@str, @b, 1),
substr(@str, @c, 1),
substr(@str, @d, 1)));

SET @d = @d + 1;
END WHILE;
SET @c = @c + 1;
END WHILE;
SET @b = @b + 1;
END WHILE;
SET @a = @a + 1;
END WHILE;



Но вообще тоже не быстро. Может быть имеет смысл генерировать динамический sql и вставлять пакетами.

ну а дальше остаётся только удалить лишние:

DELETE t FROM test AS t
INNER JOIN (
SELECT word FROM test
ORDER BY RAND()
LIMIT 0, 48576
) AS q
ON q.word = t.word;


Comments

[Ivan Komarov]

и да, не ставьте unique у поля таблицы, если нужен будет констрэйн/индекс/ключ — лучше потом добавьте.

Answer 9

[impass]

что касается работы с базой (у вас ведь MySQL наверняка?)

ALTER TABLE `something` DISABLE KEYS
несколько многорядовых INSERT (или один со всеми записями сразу, если памяти не жалко), возможно даже с DELAYED
ALTER TABLE `something` ENABLE KEYS

Answer 10

[Shedar]

Сравнение слов регистрозависимо?
Если нет, то, согласно условию, русский алфавит:
33 буквы, 4 символа — 1 185 921 значений, т.е. нужны почти все.
Можно сформировать 185 921 случайное значение которое не брать, а все сотальные влить

Comments

[Михаил]

а если условие задачи поменяется на 10 значений, то 1 185 921 сделаем и 1 185 911 удалим)

[Shedar]

Ну, требования по универсальности не выдвигались, контекст задачи не описан. Потому я предложил решение, позволяющее проверять уникальность в 5 раз меньшего количества элементов, без заморочек на то, что символов может стать не 4 а 40, и алфавит не русский, а греческий, и не миллион а 10 и не вставить а удалить и не на php а на c#)

[Shedar]

Только сейчас заметил, что выше уже предлагали сформировать все и подчистить. Виноват, был невнимателен.

Answer 11

[Сергей Наломенко]

А может вот так?

<?
$ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
$lettersCount = 4; //кол-во символов
$wordsCount = 1000000; //кол-во слов

$c = 0;

$result = array();

while(count($result) < $wordsCount && $c++ < 10)
{
$str = "";
for($i = 0; $i < $lettersCount; $i++)
$str .= $ABC[rand(0, strlen($ABC) - 1)];
$result[$str] = 1;
}

echo "Сгенерировано ".count($result)." строк";
?>