LINUX.ORG.RU

А насколько рандомен Random?

 , , , ,


0

1

Понадобилось создать для каждого объекта уникальный идентификатор. Я никогда ничем подобным не занимался, потому навелосипедил это:

public abstract class Figure {
	
	public Figure() {
		id = new Random().nextInt();
	}
	
	private int id;
	
	@Override
	public String toString() {
		String classname = getClass().getCanonicalName();
		return classname.substring(classname.lastIndexOf('.') + 1) + "@" + Integer.toHexString(id);
	}
}
Какова вероятность, что появятся два объекта с одинаковыми идентификаторами? При каждом запуске объектов с одинаковыми класснеймами примерно по паре сотен.

★★★★★

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#nextInt()

All 2^32 possible int values are produced with (approximately) equal probability.

А вообще, костыльное какое-то решение у тебя. Выдавай им по очереди идентификаторы, записывай куда-то последний.

observer ★★★
()
Последнее исправление: observer (всего исправлений: 2)

2^-31 в лучшем случае, а чего не GUID?

ebantrop
()

По идее, 2^32, достаточно.

Deleted
()
Ответ на: комментарий от observer

Спасибо.
Получается, Random никогда не даст два одинаковых значения подряд? Меня смущает тот факт, что меня каждый раз создаётся новый Random. Это не уменьшает рандомность? Откуда берётся seed?

CYB3R ★★★★★
() автор топика

В java не очень хороший рандом. SecureRandom тоже временами не очень secure, но для этой задачи использовать можно. Только хотя бы 64 бита. Вероятность коллизии всегда есть.

Но почему бы не использовать просто атомарный счетчик?

note173 ★★★★★
()
Последнее исправление: note173 (всего исправлений: 1)

Вероятность мала,но не равна нулю. В итоге ты можешь словить крайне сложноуловимый баг. Почему бы не заюзать HashMap, в качестве идентификатора будет хеш, гарантия уникальности объектов.

hippi90 ★★★★★
()
Ответ на: комментарий от CYB3R

Получается, Random никогда не даст два одинаковых значения подряд?

Вероятность крайне мала.

Меня смущает тот факт, что меня каждый раз создаётся новый Random. Это не уменьшает рандомность? Откуда берётся seed?

Есть два конструктора:

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#Random()

http://docs.oracle.com/javase/6/docs/api/java/util/Random.html#Random(long)

Можешь ему генерить рандомный seed.

observer ★★★
()

Рекомендую использовать счетчик чтобы были гарантии. Не важно откуда берется seed, если бы инстанс Random был один, то он с большей вероятностью не повторялся. Но он не thread-safe если что ;)

Используй UUID.random() или AtomicLong.increment()

vertexua ★★★★★
()
Ответ на: комментарий от vertexua

Сложно предлагать что-то более менее конструктивное, не зная, что именно хочет сделать ТС.

hippi90 ★★★★★
()
Ответ на: комментарий от hippi90

Не знаю как у вас, но мне много чего приходится хранить в БД. Это удобно. Как говорил классик: я бы все записал в БД, и даже себя, и даже пиво =)

observer ★★★
()
Ответ на: комментарий от hippi90

Мне больше нравится идея с хэшем. У меня каждый объект просто хранит от 3 до 8 переменных типа int. У каждого объекта уникальная комбинация из этих переменных, если бы были два объекта с одинаковой комбинацией, они были бы идентичными.
Как в таком случае лучше посчитать хэш?

CYB3R ★★★★★
() автор топика

Понадобилось создать для каждого объекта уникальный идентификатор.

что тебе помешало юзать статическую глобальную переменную и приватный член класса? Каждый раз при ассайне, просто private_id = ++global_id; и все, нахрена столько мучений?

hippi90 сказал про хеш, если все на столько запущено, делай хеш из значений всех членов класса, например

unt1tled ★★★★
()
Ответ на: комментарий от CYB3R

У меня каждый объект просто хранит от 3 до 8 переменных типа int.

Я бы сложил их в стринг и посчитал бы md5, это проще всего =)

В идеале, тебе нужен полиномиальный хеш, алгоритм Дюваля.

http://habrahabr.ru/post/142589/

observer ★★★
()
Последнее исправление: observer (всего исправлений: 2)

скрытые идентификаторы просто инкрементируй (2^32 когда ещё переполнишь), при публикации (читай - назначению объектам) шифруй любым приятным тебе способом.

Свойство «годности» ф-ции шифрования - шифрованный монотонный ряд должен проходить тесты на равномерное распределение.

Получится что уникальность обеспечивается инкрементом исходного идентификатора, а «псевдослучайность» его шифрованием.

MKuznetsov ★★★★★
()
Ответ на: комментарий от observer

Я бы сложил их в стринг и посчитал бы md5, это проще всего =)

это медленно и глупо, если не нужна криптография, зачем ему 128 битный хеш?

проще всего взять несколько простых чисел и написать свою функцию

unt1tled ★★★★
()
Ответ на: комментарий от observer

Да это же джава, всё сделано за меня. Вот так выглядит хорошо:

public abstract class Figure {
	@Override
	public String toString() {
		String classname = getClass().getCanonicalName();
		return classname.substring(classname.lastIndexOf('.') + 1) + "@"
				+ Integer.toHexString(hashCode());
	}
}

CYB3R ★★★★★
() автор топика

Только инкрементарный счетчик.

LeoK
()
Ответ на: комментарий от CYB3R

Рандом, точнее генератор псведослучайных чисел - это числовая последовательность, равномерно распределённая, где числа «выглядят» слычайными. Первый член последовательности - однозначно получается из твоего seed'a. Каждый следующий вызов функции random() (или getNext()) - возвращает следующий член последовательности. Для каждого seed'а у тебя будет всегда получаться одна и та же последовательность.

Фактически, random - неплохая хэш функция, если кормить ему seed в качестве ключа :)

invy ★★★★★
()
Последнее исправление: invy (всего исправлений: 3)
Ответ на: комментарий от Reset

Я не хочу использовать uuid т.к. их сложно читать. У меня это значение (зачем-то) выводится на экран.

CYB3R ★★★★★
() автор топика

Я легко могу путать, но откуда-то в памяти выплывает MT19937 у йавы.

mv ★★★★★
()

В твоём случае id = hashCode() будет надёжней рандома. Со счётчиком, конечно, лучше. Мне лень смотреть исходники, но имхуется, что рандом сидится от текущего времени и два new Random().nextInt() подряд могут выдать одно и то же.

Legioner ★★★★★
()

Если нужна уникальность в пределах одного запуска - инкремент и только. Только не забывай про thread-safety для инкремента.

Если нужна глобальная уникальность - UUID. Для отладочной печати можно скукожить в более краткую запись.

Pavval ★★★★★
()
Ответ на: комментарий от hippi90

в качестве идентификатора будет хеш, гарантия уникальности объектов.

хэш не обязан быть уникальным

MyTrooName ★★★★★
()
Ответ на: комментарий от hippi90

а я бы записал в private static int. а если нужна перзистентность, то можно и sqlite. или тот движок БД, который уже используется

MyTrooName ★★★★★
()
Ответ на: комментарий от CYB3R

аппаратный квантовый генератор рандома еще круче.

я вообще удивляюсь, ТС почти ничего не конкретизировал, а ему тут уже и хеши предлагают, и бд, и сид рандомом генерить..

MyTrooName ★★★★★
()

Давайте просто возьмём, и проверим через сколько будет коллизия…

import java.util.*;

class test {
    public static void main(String[] args) {
        int i = 0;
        Random r = new Random();
        HashSet<Integer> set = new HashSet<Integer>();
        while (true) {
            int next = r.nextInt();
            if (set.contains(next)) {
                break;
            } else {
                i += 1;
                set.add(i);
            }
        }
        System.out.println(i);
    }
}
$ for i in `seq 30`; do java test; done
46385
74635
77124
87060
152750
69924
108594
144025
150914
28097
110134
123596
65483
79068
122616
23451
90162
134238
81105
85735
83548
96561
110768
106320
124138
83998
160995
55229
100280
100503

Используй хеши или счётчик.

PolarFox ★★★★★
()
Последнее исправление: PolarFox (всего исправлений: 2)

Не надо каждый раз создавать генератор. Добавь текущее время и все будет ок.

String id = String.valueOf(System.currentTimeMillis()) + random.nextLong();

vtVitus ★★★★★
()
Ответ на: комментарий от anonymous

Странно что не первый коммент.

anonymous
()

Можно например сделать фабрику объектов, по типу:


public class SequenceFactory {

    private static int seq = 0;

    public static void main(String[] args) {
        for(int i = 0; i < 10; i++) {
            SequenceFactory.Sequence seq = SequenceFactory.getSequence();

            System.out.println(seq.toString());
        }
    }
    
    public static Sequence getSequence() {
        seq++;

        return new Sequence(seq);
    }

    public static class Sequence {

        private int seq;
        
        public Sequence(int seq) {
            this.seq = seq;
        }

        public String toString() {
            return "Seq: " + Integer.valueOf(seq);
        }
        
    }
    
}

grouzen ★★
()
Последнее исправление: grouzen (всего исправлений: 1)

Если твои объекты с идентификаторами сохраняются между рестартами приложения, то только UUID.randomUID(), для этого он и придуман. Если не сохраняются, то используй AtomicLong как инкрементный счетчик. Счетчик можно использовать и в первом варианте, но для этого где-то нужно сохранять его значение, откуда потом это значение можно считать при старте приложения.

Если сохранять ты не хочешь, то используй UUID. На экран можно выводить обрезанное строковое представления UUID'а. Например, вместо 550e8400-e29b-41d4-a716-446655440000 выводи 550e8400. Вероятность коллизии и так мала, ну а в случае возникновения программа отработает корректно, а на экране появятся 2 объекта с как бы одинаковыми id. Придумай как на экране id можно «развернуть» в полную форму при необходимости.

Ian ★★
()
Последнее исправление: Ian (всего исправлений: 2)

объединение локального инкремента и 2^64

stevejobs ★★★★☆
()
Ответ на: комментарий от CYB3R

Вы что тервер прогуливали?
Может дать и два подряд , три подряд, 1000 подряд

Используйте гуид для идентификаторов, или через счетчик.

d_Artagnan ★★
()

Прочитал тред и не понял. Для чего огород городить? Каждый объект и так имеет хеш. Зачем нужен еще один?

vada ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.