VPF::HashMap. Тестирование алгоритма UnionFind.

Tiala

Дата 31.7.2013, 17:03 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 1
Регистрация: 28.7.2008

Репутация: нет
Всего: нет

Здравствуйте. Есть небольшая проблемка которую не могу решить. Есть стандартный алгоритм UnionFind, часть кода приведена ниже:

Код


private final Map<EntryType, EntryType> parentMap;
private final Map<EntryType, Integer> rankMap;

    // Create an empty union find data structure with isolated sets.

    public UnionFindAlgorithm(final Set<EntryType> elements) {
        parentMap = new HashMap<EntryType, EntryType>();
        rankMap = new HashMap<EntryType, Integer>();
        for (final EntryType element : elements) {
            parentMap.put(element, element);
            rankMap.put(element, 0);
        }
    }

    public void addElement(final EntryType element) {
        parentMap.put(element, element);
        rankMap.put(element, 0);
    }

    protected Map<EntryType, EntryType> getParentMap() {
        return parentMap;
    }

    protected Map<EntryType, Integer> getRankMap() {
        return rankMap;
    }

    // Return parent for element

    public EntryType find(final EntryType element) {

        final EntryType parent = parentMap.get(element);
        if (parent.equals(element)) {
            return element;
        }

        final EntryType newParent = find(parent);
        parentMap.put(element, newParent);
        return newParent;
    }

    // merge components containing element1 and element2
    public void union(final EntryType element1, final EntryType element2) {

        final EntryType parent1 = find(element1);
        final EntryType parent2 = find(element2);

        // check if the elements are already in the same set
        if (parent1.equals(parent2)) {
            return;
        }
        final int rank1 = rankMap.get(parent1);
        final int rank2 = rankMap.get(parent2);
        if (rank1 > rank2) {
            parentMap.put(parent2, parent1);
        } else if (rank1 < rank2) {
            parentMap.put(parent1, parent2);
        } else {
            parentMap.put(parent2, parent1);
            rankMap.put(parent1, rank1 + 1);
        }

    }

Проблема в том, что я хочу создать собственную Хэш-таблицу, но для каждого ключа при этом сопоставить то значение которое я хочу. В данном случае при ключе равным 1, значение будет 1, т.е. 1=1. а мне допустим надо 1=5. Значения должны быть произвольными и размер массива тоже разный, так как я тестирую time complexity для данного алгоритма.

Пока что есть только вот это:

Код


    public static void main(final String[] args) {
        final Set<Integer> set1 = new HashSet<Integer>();

        final Random r = new Random();
        for (int f = 10; f < 80; f = 2 * f) {
            for (int i = 0; i < f; i++) {
                set1.add(i);
            }

            final List<Integer> set2 = new ArrayList<Integer>();
            for (int i = 0; i < f; i++) {
                set2.add(r.nextInt(f / 2));
            }

            final long lBegin = System.currentTimeMillis();

            final UnionFindAlgorithm<Integer> u = new UnionFindAlgorithm<Integer>(
                    set1);
            final Integer[] set3 = set1.toArray(new Integer[set1.size()]);
            for (int i = 0; i < f; i++) {
                u.parentMap.put(set3[i], set2.get(i));
            }

            System.out.println(u.parentMap);
            final long lEnd = System.currentTimeMillis();
            final long lDelta = lEnd - lBegin;

            set1.removeAll(set1);
            set2.removeAll(set2);
        }

Но как итог я не могу воспользоваться методом Find, выдается ошибка. Помогите понять что не так, и как я могу это исправить. Всем спасибо за внимание. Если что то надо дополнительное - спрашивайте.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Java: Общие вопросы \| Следующая тема »