Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Перебор массива/коллекции

Автор: tepkuh 13.5.2010, 16:42

Добрый день уважаемые,
Я вот который час подряд уже бьюсь с эффективным способом перебора массива. Ну никак не выходит что то красивое, помогите плиз.
Суть такая:
Есть коллекция HashMap<String, Set>
Выглядит так:
1->[a,b,c,d]
2->[s,r,h,j,k,l,a,...]
3->[v,x,g,q,a,z,p,a...]
4->[x,f,a,c,e,y...]

Длинна ХэшМапа большая, может измеряться сотнями столбцов. Длинна Set измеряется десятками\сотнями позиций.
Каждый столбец и каждая позиция используется только один раз,
например первая итерация:
a+s+y+x
Вторая
a+s+y+f
Третья
a+s+y+a
и так далее...
Если пробую рекурсию ухожу в нехватку стека. Увеличивать стек не вариант ибо не красиво)

Памажите идей плиз)

Автор: AntonSaburov 13.5.2010, 18:30

Не очень понятно, что за алгоритм надо реализовать. Из примера ничего не понял.
Какие столбцы и какие позиции ? Где они ? В Set ? В каждом ? Или в разбивку ?

Автор: Sibit 14.5.2010, 05:51

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

А что в результате получить нужно?

Автор: MisterCleric 14.5.2010, 09:43

Цитата

А что в результате получить нужно?

Я так думаю хочет написать программку подбора паролей...

По-моему, надо милицию вызывать

Автор: tepkuh 14.5.2010, 11:27

Цитата(AntonSaburov @ 13.5.2010, 18:30)

Да тут без поллитры не объяснить)
Надо просто перебрать все столбцы и строки по сути. У меня массив просто в виде коллекции где строки это коллекция Set, а столбцы это коллекция Map.
Т.е. у меня есть таблица определенного количества строк, каждая строка в таблице имеет разное число столбцов, выглядит примерно так:

Код


1|a|b|c|d|
2|s|r|h|j|k|a|
3|v|x|g|q|a|z|p|

Так же оговорюсь что таблица это может быть большой и она динамическая(может иметь разное количество строк и столбцов, как большое число строк\столбцов так и малое), настолько большой, что рекурсией перебрать не получится, просто не хватает стека. Т.е. это у нас данные.

Перебор данных осуществляется так что берется только одно значение из каждой строки.

Показываю свой индус-код, чисто поржать, но ничего умнее не идет.

Код


public static void main(String[] args){

        Map<String,Set> tmp_map = new TreeMap<String,Set>();//По сути это строки массива
        Set<String> tmp_set1 = new TreeSet<String>();//Столбецы 
        Set<String> tmp_set2 = new TreeSet<String>();//Столбецы 
        Set<String> tmp_set3 = new TreeSet<String>();//Столбецы 
        tmp_set1.add("a1");//Ячейка первой строки, 1го стольбца
        tmp_set1.add("b1");//Ячейка первой строки, 2го стольбца
        tmp_set1.add("c1");//Ячейка первой строки, 3го стольбца
        tmp_set1.add("d1");//Ячейка первой строки, 4го стольбца

        tmp_set2.add("a2");//Ячейка второй строки, 1го стольбца
        tmp_set2.add("b2");//Ячейка второй строки, 2го стольбца
        tmp_set2.add("c2");//Ячейка второй строки, 3го стольбца
        tmp_set2.add("d2");//Ячейка второй строки, 4го стольбца
        tmp_set2.add("e2");//Ячейка второй строки, 5го стольбца
        tmp_set2.add("f2");//Ячейка второй строки, 6го стольбца

        tmp_set3.add("a3");
        tmp_set3.add("b3");
        tmp_set3.add("c3");
        tmp_set3.add("d3");
        tmp_set3.add("e3");       

        tmp_map.put("1", tmp_set1);
        tmp_map.put("2", tmp_set2);
        tmp_map.put("3", tmp_set3);
        
        //Дальше можно смеяться, пошел идус-код, преобразую Map в Аrray, потому что с Итератором в данном случаи не удобно работать, так как его просто фиг склонируешь.
        Object[] objectArray = tmp_map.entrySet().toArray();
        Vector result = new Vector(); //Сюда мы пишем результат
        Plunk2(objectArray, result);//Собственно индус функция

public static void Plunk2(Object[] obj, Vector result) {
        try{
            //Выводим результат на экран 
            if (obj.length-1<0){
                for(int i=0;i<result.size();i++){
                    System.out.print(result.get(i));
                }
                System.out.println();
                return;
            }
            //Убираем одну строку из нашего массива с данными
            Object[] obj2 = new Object[obj.length-1];
            for(int i=1;i<obj.length;i++){
                obj2[i-1] = obj[i];
            }
            //Мега индус-рекурсия тут осуществляется
            for(int i=0;i<obj.length;i++){
                Map.Entry entry = (Map.Entry)obj[i];
                Set synons = (Set)entry.getValue();
                Iterator iter_synons = synons.iterator();
                while(iter_synons.hasNext()){
                    String synon = (String)iter_synons.next();
                    result.add(synon);
                    Plunk2(obj2,result);
                    result.remove(result.lastElement());
                }
            }
        }
        catch (Exception q) {
            q.printStackTrace();
        }
    }

Код


сам результат работы моей магии кода:
a1a2a3
a1a2b3
a1a2c3
a1a2d3
a1a2e3
a1b2a3
a1b2b3
a1b2c3
a1b2d3
a1b2e3
a1c2a3
a1c2b3
a1c2c3
a1c2d3
a1c2e3
a1d2a3
a1d2b3
a1d2c3
a1d2d3
a1d2e3
a1e2a3
a1e2b3
a1e2c3
a1e2d3
a1e2e3
a1f2a3
a1f2b3
a1f2c3
a1f2d3
a1f2e3
a1a3a3
a1a3b3
a1a3c3
a1a3d3
a1a3e3
a1b3a3
a1b3b3
a1b3c3
a1b3d3
a1b3e3
a1c3a3
a1c3b3
a1c3c3
a1c3d3
a1c3e3
a1d3a3
a1d3b3
a1d3c3
a1d3d3
a1d3e3
a1e3a3
a1e3b3
a1e3c3
a1e3d3
a1e3e3
b1a2a3
b1a2b3
...

Добавлено @ 11:35

Цитата(MisterCleric @ 14.5.2010, 09:43

)

Я так думаю хочет написать программку подбора паролей...

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

Автор: pathfinder 14.5.2010, 12:19

Почти псевдокод )

Код


int mapSize = map.size();

Object[][] setArray;
int[] indexArray;
int[] setLengthArray;

Object[] resultArray;

// todo : перегнать Map -> setArray
// todo : инициализировать setLengthArray: setLengthArray[i] = i-ой Set.size()

main_loop:
while (true) {
    
    // собираем результат
    for (int i=0; i<mapSize; i++) {
        resultArray[i] = setArray[i][indexArray[i]];
    }
    
    // обрабатываем результат ...
    
    // увеличиваем индексы сверху-вниз ...
    for (int i=0; i<mapSize; i++) {
        indexArray[i] = indexArray[i] + 1;
        if (indexArray[i] < setLengthArray[i]) {
            break;
        }
        indexArray[i] = 0;
        if (i + 1 == mapSize) {
            break main_loop;
        }
    }
    
}

Автор: tepkuh 14.5.2010, 12:59

Цитата(pathfinder @ 14.5.2010, 12:19

)

// todo : перегнать Map -> setArray

кхм... думал об этом.
У меня размерность таблицы моей может доходить до нескольких тысяч строк вниз, и столько же вправо.
Для того чтобы их перегнать(а я так понял их перегонять только циклом) это должен крутануть цикл до нескольких лимонов раз. Только на инициализацию setArray.
Мой Индус-код быстрее получится даже имхо так как Вам этот цикл надо крутать дважды(перегнон в setArray) а дальше еще пройтись по каждой ячейки

Автор: pathfinder 14.5.2010, 13:22

А если так

Код


int mapSize = map.size();

Set[] setArray = new Set[mapSize];
Iterator[] iteratorArray = new Iterator[mapSize];
Object[] resultArray = new Object[mapSize];

// todo заполнить setArray из Map
// todo заполнить iteratorArray: iteratorArray[i] = setArray[i].iterator();

for (int i=0; i<mapSize; i++) {
    resultArray[i] = iteratorArray[i].next();
}

main_loop:
while(true) {
    
    // handle resultArray ...
    
    for (int i=0; i<mapSize; i++) {
        if (iteratorArray[i].hasNext()) {
            resultArray[i] = iteratorArray[i].next();
            break;
        } else {
            if (i + 1 == mapSize) {
                break main_loop;
            }
            iteratorArray[i] = setArray[i].iterator();
            resultArray[i] = iteratorArray[i].next();
        }
    }
}

Автор: tepkuh 14.5.2010, 13:58

у меня дает результат 825 вариантов перебора, у вас 155 =). Выпадает чиво то)

Код Ваш с Инициализацией:

Код


        int mapSize = tmp_map.size();
        Set[] setArray = new Set[mapSize];
        Iterator[] iteratorArray = new Iterator[mapSize];
        //Пошла Инициализация
        Iterator iter = tmp_map.entrySet().iterator();
        int k=0;
        while(iter.hasNext()){
            setArray[k]=  (Set)((Map.Entry)iter.next()).getValue();
            iteratorArray[k] = setArray[k].iterator();
            k++;
        }
         //Кончилась Инициализация 
        Object[] resultArray = new Object[mapSize];
        for (int i=0; i<mapSize; i++) {
            resultArray[i] = iteratorArray[i].next();
        }
        for(int q=0;q<resultArray.length;q++){
            System.out.print(resultArray[q]);
        }
        System.out.println();

        main_loop:
        while(true) {
            // handle resultArray ...
            for (int i=0; i<mapSize; i++) {
                if (iteratorArray[i].hasNext()) {
                    resultArray[i] = iteratorArray[i].next();
                    for(int q=0;q<resultArray.length;q++){
                        System.out.print(resultArray[q]);
                    }
                    System.out.println();
                    break;
                }
                else {
                    if (i + 1 == mapSize) {
                        break main_loop;
                    }
                    iteratorArray[i] = setArray[i].iterator();
                    resultArray[i] = iteratorArray[i].next();
                    for(int q=0;q<resultArray.length;q++){
                        System.out.print(resultArray[q]);
                    }
                    System.out.println();
                }
            }
        }

Добавлено через 11 минут и 21 секунду
+у вас идут повторения переборов) где то ошибка у Вас в коде) Пытаюсь воткнуть что хотели написать)ы

Автор: pathfinder 14.5.2010, 14:14

Для просмотра результата надо подставить

Код


for(int q=0;q<resultArray.length;q++){
                        System.out.print(resultArray[q]);
                    }
                    System.out.println();

вместо

Код


// handle resultObject

и вопрос в догонку - при количестве колонок около 1000 и количестве элементов в колонке > 10, разве потребное количество итераций не будет пропорционально 10^1000(или точнее произведению длин колонок)?

Автор: tepkuh 14.5.2010, 14:38

Цитата(pathfinder @ 14.5.2010, 14:14

)

или точнее произведению длин колонок

да, точное произведение длин всех колонок) Итераций много) выйдет. Но это даже хорошо) Чем их больше тем я буду счастливей.
Спасибо вам большое действительно все работает) (это у меня не работало))Вы очень очень мне помогли)

Автор: pathfinder 14.5.2010, 15:25

Всегда пожалуйста ) Если вопрос решен тему желательно закрывать.

Автор: tepkuh 15.5.2010, 11:37

Помечаем что вопрос решен)