Что было бы лучшим алгоритмом для нахождения идентификатора, который не используется от таблицы, которая имеет возможность содержать миллион строк
Используйте это, чтобы получить круговое изображение с границей -
public static Bitmap getCircularBitmapWithBorder(Bitmap bitmap, int bordercolor) {
if (bitmap == null || bitmap.isRecycled()) {
return null;
}
int borderWidth=(int)(bitmap.getWidth()/40);
final int width = bitmap.getWidth() + borderWidth;
final int height = bitmap.getHeight() + borderWidth;
Bitmap canvasBitmap = Bitmap.createBitmap(width, height,
Bitmap.Config.ARGB_8888);
BitmapShader shader = new BitmapShader(bitmap, TileMode.CLAMP,
TileMode.CLAMP);
Paint paint = new Paint();
paint.setAntiAlias(true);
paint.setShader(shader);
Canvas canvas = new Canvas(canvasBitmap);
float radius = width > height ? ((float) height) / 2f
: ((float) width) / 2f;
canvas.drawCircle(width / 2, height / 2, radius, paint);
paint.setShader(null);
paint.setStyle(Paint.Style.STROKE);
paint.setColor(bordercolor);
paint.setStrokeWidth(borderWidth);
canvas.drawCircle(width / 2, height / 2, radius - borderWidth / 2,
paint);
return canvasBitmap;
}
18 ответов
Вопрос, конечно: почему Вы хотите случайный идентификатор?
Один случай, где я встретился с подобным требованием, был для клиентских идентификаторов веб-приложения: клиент отождествляет себя со своим клиентским идентификатором (сохраненный в cookie), таким образом, это должно быть твердо к предположению грубой силы идентификатор другого клиента (потому что это позволило бы угонять его данные).
Решение, с которым я пошел, должен был объединить последовательный int32 со случайным int32 для получения int64, который я использовал в качестве клиентского идентификатора. В PostgreSQL:
CREATE FUNCTION lift(integer, integer) returns bigint AS $$
SELECT ($1::bigint << 31) + $2
$$ LANGUAGE SQL;
CREATE FUNCTION random_pos_int() RETURNS integer AS $$
select floor((lift(1,0) - 1)*random())::integer
$$ LANGUAGE sql;
ALTER TABLE client ALTER COLUMN id SET DEFAULT
lift((nextval('client_id_seq'::regclass))::integer, random_pos_int());
Сгенерированные идентификаторы 'наполовину' случайны, в то время как другая 'половина' гарантирует, что Вы не можете получить тот же идентификатор дважды:
select lift(1, random_pos_int()); => 3108167398
select lift(2, random_pos_int()); => 4673906795
select lift(3, random_pos_int()); => 7414644984
...
Лучший алгоритм в этом случае должен генерировать случайное число и сделать выбор, чтобы видеть, существует ли он, или просто попытайтесь добавить его, если Ваша база данных допускает ошибку нормально. В зависимости от диапазона Вашего ключа, по сравнению с, сколько там записи, это могло быть небольшим количеством времени. Это также имеет способность пронзить и не последовательно вообще.
Было бы возможно выполнить некоторые запросы на BigTable и видеть, существуют ли какие-либо диапазоны, которые могли бы быть использованы? т.е. между 100 000 и 234,000 еще нет никакого идентификатора, таким образом, мы могли добавить идентификатор там?
Пропуская обоснование самой задачи, единственный алгоритм это
- даст Вам идентификатор не в таблице
- это будет использоваться для вставки новой строки в таблицу
- приведет к таблице, все еще имеющей случайные уникальные идентификаторы
генерирует случайное число и затем проверяет, используется ли оно уже
Сначала проверьте, не взят ли Max (Айдахо) + 1, и используйте это.
Если Max (Айдахо) + 1 превышает максимум, затем выбирают заказанный блок наверху и запускают цикличное выполнение, назад ища дыру. Повторите блоки, пока у Вас не заканчиваются числа (в этом случае бросают большую ошибку).
если "дыра" найдена, затем сохраняют идентификатор в другой таблице, и можно использовать это в качестве начальной точки для следующего случая для сохранения цикличного выполнения.
Действительно ли это - требование что новый идентификатор также быть случайным? Если так, лучший ответ должен только циклично выполниться по (рандомизируйте, тест для существования), пока Вы не находите тот, который не существует.
Если данные просто, оказывается, случайны, но это не сильное ограничение, можно просто использовать ВЫБОР МАКС (idcolumn), увеличить в некотором роде соответствующий данным и использованию что как первичный ключ для следующей записи.
Необходимо сделать это атомарно, таким образом, или блокировка таблица или использует некоторое другое управление совместным выполнением, соответствующее конфигурации DB и схеме. Сохраненные procs, блокировки таблицы, блокировки строки, ВЫБИРАЮТ... FOR UPDATE, безотносительно.
Обратите внимание, что в любом подходе Вы, возможно, должны обработать отказавшие транзакции. Можно теоретически получить дублирующиеся ключевые вопросы в первом (хотя это маловероятно, если ключевое пространство является малонаселенным), и Вы, вероятно, получите мертвые блокировки на некотором DBS с подходами как ВЫБОР... FOR UPDATE. Так обязательно проверьте и перезапустите транзакцию на ошибке.
Это - вероятно, плохая идея просканировать каждое значение в той таблице, каждый раз ища уникальное значение. Я думаю способ сделать, это должно было бы иметь значение в другой таблице, соединить ту таблицу, считать значение, вычислить значение следующего идентификатора, записать значение следующего идентификатора, выпустить блокировку. Можно затем использовать идентификатор, который Вы читаете с уверенностью, Ваш текущий процесс является единственным, содержащим что уникальное значение. Не уверенный, как хорошо это масштабируется.
Кроме того, используйте GUID для своих идентификаторов, так как каждый недавно сгенерированный GUID, как предполагается, уникален.
в зависимости от Вашей базы данных у Вас могла бы быть опция или использования секвенсера (оракул) или автоинкремента (mysql, мс sql, и т.д.). Или последнее средство делает выбор, макс. (идентификатор) + 1 как новый идентификатор - просто остерегаться параллельных запросов, таким образом, Вы не заканчиваете с тем же макс. идентификатором дважды - переносят его в блокировку с предстоящим оператором вставки
Если идентификатор чисто случаен, нет никакого алгоритма для нахождения неиспользованного идентификатора столь же случайным способом без грубого принуждения. Однако, пока битовая глубина Вашего случайного уникального идентификатора является довольно большой (скажите, что 64 бита), Вы довольно в безопасности от коллизий только с миллионом строк. Если это сталкивается на вставке, просто попробуйте еще раз.
Я видел сделанный так много раз прежде через грубую силу, с помощью генераторов случайных чисел, и это всегда - плохая идея. Генерация случайного числа за пределами дб и попытка видеть, существует ли это, поместят большую деформацию в Ваше приложение и базу данных. И это могло привести к 2 процессам, выбирающим тот же идентификатор.
Ваш наилучший вариант состоит в том, чтобы использовать автоинкрементную способность MySQL. Другие базы данных имеют схожую функциональность. Вам гарантируют уникальный идентификатор и не будете иметь проблем с параллелизмом.
Первый вопрос: это запланированная база данных или уже функциональная. Если это уже имеет данные внутри затем, ответ bmdhacks корректен. Если это - запланированная база данных, вот второй вопрос:
Ваш первичный ключ должен действительно быть случайным? Если ответ - да, затем используют функцию для создания случайного идентификатора из с известным семенем, и в противоречии со знают, сколько Ids было создано. Каждый созданный идентификатор увеличит счетчик.
Если Вы держите семя в секрете (т.е. назовите семя и объявленный частным), затем никто больше не должен мочь предсказать следующий идентификатор.
Выберите случайное число, проверьте, существует ли оно уже, раз так затем продолжайте пробовать, пока Вы не поражаете тот, который не делает.
Править: Или еще лучше, пропустите проверку и просто попытайтесь вставить строку с различными идентификаторами, пока она не будет работать.
Если это будет чем-то, что необходимо будет часто делать, то Вы, вероятно, захотите поддержать живое (недб) структура данных, чтобы помочь Вам быстро ответить на этот вопрос. Дерево с 10 путями было бы хорошо. Когда приложение запускается, оно заполняет дерево путем чтения ключей из дб, и затем сохраняет его в синхронизации с различными вставками и удаляет сделанный в дб. Пока Ваше приложение является единственным, обновляющим дб, с деревом можно консультироваться очень быстро при проверке, что следующий большой случайный ключ уже не используется.
Сделайте поле ключа УНИКАЛЬНЫМ и ИДЕНТИФИКАЦИОННЫЕ ДАННЫЕ и Вы, привычка должна волноваться об этом.
Немного за пределами поля.
Почему бы не предварительно генерировать Ваши случайные числа заранее? Тот путь при вставке новой строки в bigtable, проверка, был уже сделан. Это сделало бы, вставляет в bigtable постоянную операцию времени.
Необходимо будет выполнить проверки в конечном счете, но это могло быть разгружено к второму процессу, который не включает чувствительный процесс вставки в bigtable.
Или пойдите, генерируют несколько миллиардов случайных чисел и удаляют дубликаты, затем Вы не должны будете волноваться в течение достаточно долгого времени.
Ваш лучший выбор состоит в том, чтобы сделать Ваше ключевое пространство достаточно большим, что вероятность коллизий является чрезвычайно низкой, затем не волнуйтесь об этом. Как упомянуто, GUID сделают это для Вас. Или, можно использовать чистое случайное число, пока оно имеет достаточно битов.
Эта страница имеет формулу для вычисления вероятности коллизии.
Нет действительно хорошего алгоритма для этого. Можно использовать эту основную конструкцию для нахождения неиспользованного идентификатора:
int id;
do {
id = generateRandomId();
} while (doesIdAlreadyExist(id));
doSomethingWithNewId(id);
Почему уникальный идентификатор Случаен? Почему бы не использовать ИДЕНТИФИКАЦИОННЫЕ ДАННЫЕ? Как идентификатор был выбран для существующих строк.
Самая простая вещь сделать, вероятно (Select Max (Айдахо) от BIGTABLE), и затем удостоверьтесь, что Ваш новый "Случайный" идентификатор больше, чем это...
Править: На основе добавленной информации я предположил бы, что Вы завинчены.
Если это - опция: Скопируйте таблицу, затем переопределите ее и используйте Столбец Идентификационных данных.
Поскольку другой ответ размышлял, при необходимости в действительно случайном Идентификаторе: сделайте свой PK двумя полями. Поле Идентификационных данных и затем случайное число.
Если Вы просто не можете изменить проверку структуры таблиц, чтобы видеть, существует ли идентификатор прежде, чем попробовать вставку, вероятно, Ваше единственное обращение за помощью.
Почему бы не добавить в создатель случайных чисел текущую дату в секундах. Таким образом, единственный способ иметь идентичный идентификатор - это если два пользователя будут созданы в одну и ту же секунду и получат один и тот же случайный номер от вашего генератора.