Найефективніший спосіб пошуку структури даних у багато-дерева

I am wondering if there is a more efficient way to search through a multi-tree than what I have been doing. I recently built a multi-tree data structure for a project that is illustrated below. Multi-Tree data structure using ArrayLists

Печера буде тримати сторони в списку масивів. Різні партії будуть тримати різні істоти. Різні істоти будуть тримати різні предмети.

Мені потрібен спосіб пошуку всього дерева, щоб відповідати об'єкту атрибуту, такого як індекс. Це фрагмент моєї програми, який шукає через кожен ArrayList, щоб побачити, чи будь-яка сторона, істота, скарб, або артефакт відповідає індексу int I called.

Edit(Explaining my code) The classes Party, Creature, Treasure, and Artifact all have attributes such as index, name, type, etc. The multi-tree has the Cave set as the root note. Cave has an ArrayList that can contain a number of Party objects. Each Party has an ArrayList that can contain a a number of Creature objects. Each creature has two array lists one to hold Artifact objects and one for Treasure objects.

Нижче я шукаю, щоб побачити, яка партія, істота, артефакт чи скарб має певний індекс, який я шукаю. Я роблю це, повторюючи партії, з кожною стороною я дивлюся на істоти, і з кожним творінням дивлясь на артефакти та скарби. Ось чому у мене так багато для циклів всередині для циклів :(.

case 0 :
            int index =                 Integer.parseInt( stat );
            for ( Party p : SorcerersCave.theCave.parties ) {
                if ( index == p.getIndex()) {
                    generateInterface.theGame.printOutput( "\t" + p );
                    break;
                } else {
                    for ( Creature c : p.members ){
                        if ( index == c.getIndex() ){
                            generateInterface.theGame.printOutput( "\t" + c );
                            break;
                        } else {
                            for ( Treasure t : c.inventory ){
                                if ( index == t.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + t );
                                    break;
                                }
                            }
                            for ( Artifact a : c.artifacts ){
                                if ( index == a.getIndex() ){
                                    generateInterface.theGame.printOutput( "\t" + a );
                                    break;
                                }
                            }
                        }
                    }
                }
            }

Я відчуваю, що цей код занадто складний, і його важко дотримуватися. Код працює, але його потворна пляма на моєму інакше дійсно гарному коді. Я дивлюся, щоб знайти кращий спосіб зробити це, або навіть спосіб покращити його.

Примітка * Вимоги до проекту забороняють нам розміщувати кожен об'єкт у тій самій системі ArrayList.

5
Я не мав ідеї там де інструменти що могли розповісти вам як складний ваш код! Не можу чекати, щоб випробувати його. Що сказала, я пробіг через це на папері, і я не бачу іншого способу, ніж велосипед, як я вже зробив вище. Я відносно молодий програміст, тому я все ще намагаюся створити свій набір інструментів і знання.
додано Автор Dustin E., джерело
Я беру ставку на цикломатичні аналізатори складності, просто збираюся любити цього коду ... З усією серйозністю, давайте уникати коду Java і перерахувати цілі алгоритму на папері. Якщо ви можете це зробити, ви можете з'ясувати трохи чистий спосіб/підхід до цієї проблеми. По суті, я не бачу жодного "дерева" - насправді фрагмент коду, який ви надали, недостатній, щоб дати вам хорошу відповідь. Не могли б ви навести контекст для коду, який ви маєте тут, наприклад, які правила ви нав'язуєте?
додано Автор Makoto, джерело
@ isaach1000: break вийде з циклу на цьому рівні . Висловлювання вищих рівнів break вириваються з циклів вищого рівня.
додано Автор Makoto, джерело
Точно, але не має сенсу знайти перший матч, будь то партія чи істота тощо?
додано Автор isaach1000, джерело
Я думаю, що перерва вийде з внутрішньої петлі.
додано Автор isaach1000, джерело
Якщо getIndex є загальним методом для всіх класів, чи ви вважаєте, що абстрагувати його до супер класу? один остаточний курорт може використовувати інстакції або відображення, якщо вам це абсолютно необхідно.
додано Автор Seshadri Sastry, джерело

7 Відповіді

Вимоги проекту забороняють нам розміщувати кожен об'єкт у тій же "ArrayList".

(І, мабуть, заборонено теж HashMap або TreeMap ...)

Без будь-якої вторинної структури даних для відображення значень index до об'єктів, до яких вони посилаються, у вас є вибір , але для переміщення дерева. Отже, в середньому код вашого "знайдіть об'єкт" буде O (N) , якщо є об'єкти N з досить великою константою пропорційності.

(Мабуть, кожен, хто розмістив це обмеження на проблемі, не піклувався про ефективність. Ви повинні мати таке саме відношення ... особливо, якщо врахувати контекст, викладений у ваших коментарях.)

Ви можете покращити код декількома способами, що зробить його більш читабельним та (найімовірніше) більш ефективним.

  1. Використовуйте "break to label", щоб внутрішні цикли виходили до кінця зовнішнього циклу, коли вони отримали удар. (Якщо припустити, що ви хочете.)

  2. Використовуйте тимчасові змінні, щоб уникнути оцінки кількох викликів методу при кожному пошуку елемента в ієрархії контейнера. UPDATE : схоже, що ви щойно переробили код, щоб зробити це ...


... вимоги до проекту передбачають, що кожен об'єкт повинен бути інстанцією в структурі даних з декількома деревами, як показано на схемі, яку я опублікував.

Але чи вони прямо забороняють вторинну структуру даних? Або ви просто припускали , що вам не дозволено це робити?

2
додано
Насправді для вас тут важливий урок. У реальному світі це часто випадок, коли ефективність не є важливим критерієм для проекту розробки програмного забезпечення. часто важливіше, що код працює, відповідає вимогам функціональних , підтримується та доставляється вчасно. І якщо продуктивність не важлива, не варто витрачати свій час (і боси гроші), оптимізуючи.
додано Автор Stephen C, джерело
@Dustin - Він каже вам "ефективність не має значення" для цієї вправи. Це програма програмування , а не проект створення наступного додатка D & D для вбивць (або будь-якого іншого). Зробіть вправу ... і рухайтеся далі.
додано Автор Stephen C, джерело
@Dustin Я думаю, що ви подивитеся в наступному семестрі, але якщо вам цікаво і хочеш сьогодні дізнатись щось нове і важче (знову), подивіться, що таке Хеш карти здатні. Ідея полягає в тому, що у вас є один HashMap містить всі елементи дерева, де index буде ключами. Таким чином, ви зможете миттєво здійснювати пошук у всьому дереві ( O (1) ) в одному рядку коду, а не лінійно ( O (n) ) у вкладеному для циклів і/або виклик методу. Найкраща структура даних завжди залежить від її використання.
додано Автор Petr Janeček, джерело
Необов'язково задовольняти вимогам проекту щодо створення вторинної структури даних. Я запитав у професора те саме питання, і він відповів, набравши 34 рази "ні" у відповідь, не пояснюючи нічого.
додано Автор Dustin E., джерело

Ваші класи можуть реалізувати загальний інтерфейс SearchableByIndex , який буде виглядати таким чином і який буде реалізовано кожним класом у дереві:

public interface SearchableByIndex {
    public SearchableByIndex searchByIndex(int index);
    public int getIndex();
}

Потім для цього потрібен код Cave , Party і Creature :

public SearchableByIndex searchByIndex(int index) {
    if (getIndex() == index) {
        return this;
    } else {
        for (Party party : parties) {   //or Creature creature : members etc.
            SearchableByIndex found = party.searchByIndex(index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}

Версія скарбів і артефактів:

public SearchableByIndex searchByIndex(int index) {
    return (getIndex() == index) ? this : null;
}

І замість вашого вкладеного циклу ви там, у вас є

case 0:
    int index = Integer.parseInt(stat);
    SearchableByIndex foundItem = SorcerersCave.theCave.searchByIndex(index);
    if (foundItem != null) {
        generateInterface.theGame.printOutput("\t" + foundItem);
    } else {
       //print out that the item was not found
    }
    break;

Хоча метод searchByIndex() у кожному класі може здаватися повторюваним, це - це метод OOP для цього. Таким чином, кожен клас буде дбати про пошук всього його вмісту. У вашому випадку для всіх класів код буде дуже схожим (тільки зміна буде лінією для циклу), але ви можете вважати це випадковою - будь-який клас може містити будь-які дані, які він хоче, і ніякі інші класи не повинні турбуватися про те, як він зберігає свої дані.

Надалі, якщо одне з ваших класів матиме більше даних ( Treasure , Artifact і Hostage ?) Або ви хочете змінити структуру його даних (див. HashMap , якщо ви можете!), вам просто доведеться змінити метод searchByIndex() у певному класі.

Крім того, лише клас, що містить дані, повинен знати як містить його. Те, як у вас є зараз, якийсь інший клас, який викликає пошук, точно знає, як дані зберігаються в кожному класі - це не повинно бути. Якщо один клас змінюється, він порушує внутрішній код інших класів. Наприклад, клас Cave повинен вказати в своїй документації, що він містить, наприклад, різні приклади Party , і він може видати деякі з них, якщо ви шукаєте його за допомогою searchForIndex() .

2
додано
@Dustin Електронні листи є приватними, тому я не можу бачити вас. Напишіть мені> JanecekPetr squigglyAtSign seznam.cz
додано Автор Petr Janeček, джерело
@ Slanec- Чи в будь-якому разі ви можете надіслати мені листа? У мене є кілька питань про HashMap, які, на мою думку, виходять за рамки цього питання. Мій електронний лист відображається в моєму профілі.
додано Автор Dustin E., джерело

Це досить непарний набір обмежень, але в дусі перехрещення дерев, не потребуючи взагалі змінювати вихідну структуру даних, чому б не написати наївну рекурсивну функцію переміщення як набір перевантажених методів? Це може виглядати так:

public Object search(int index, Cave c) {
  if (c.id == index) return c;

  for (Party p : c.parties) {
    Object result = search(index, p);
    if (result != null) 
      return result;
  }

  return null;
}

public Object search(int index, Party p) {
  ...
}

І так далі.

1
додано
З зміною OP (для кожного циклу замість звичайних індексованих циклів), він голосно кричить за рекурсію, як це.
додано Автор Petr Janeček, джерело
Дійсно Як правило, це представлено як підручник для переміщення дерев.
додано Автор Gian, джерело

Я б мав використовувати для кожного циклу замість:

int index = Integer.parseInt(stat);
for(Party party : parties){
    if( index == party.members.get( c ).getIndex() ){
        generateInterface.theGame.printOutput( "\t" + party.summary );
        break;
    } else {
        for(Creature creature : party.Creatures){
           //etc etc.....
        }
    }
}

Це полегшить читання коду. У нього є той недолік, що у вас немає лічильника, вбудованого в цикл.

EDIT: This article may clarify: https://blogs.oracle.com/CoreJavaTechTips/entry/using_enhanced_for_loops_with

1
додано
Я не знав про кожен конструкт. Моє єдине питання до цього полягає в тому, якщо у мене є кілька партій, кожен заповнений різними істотами, як би це шукати істоти кожної партії? І скарби і артефакти кожної істоти?
додано Автор Dustin E., джерело
Див .: blogs.oracle.com/CoreJavaTechTips/entry/… Це може допомогти.
додано Автор maxf130, джерело

Перший пошук по глибині за допомогою допоміжного методу.

private Interface IndexObject
{
   //Interface will be used in dfsList
    public int getIndex();
}

private Interface ListObject extends IndexObject
{
   //For classes with sublists
    public ArrayList getList();
}

public void search(int index) {
    Object found = dfsList(parties, index);
}

// Helper method
public Object dfsList(ArrayList aList, int index) {
    for (IndexObject obj : aList) {
        if (obj.getIndex() == index) {
            return obj;
        }
        else if (obj instanceof ListObject) {
            IndexObject found = dfsList(obj.getList(), index);
            if (found != null) {
                return found;
            }
        }
    }
    return null;
}
0
додано

Не могли б ви використати більш регулярну структуру? Щось подібне (я використовую псевдокод):

interface INode { ... stuff kept in nodes is described here ... }
interface ITree extends INode { bool HasId(int id); ITree[] Children; }

INode SearchTreeForId(ITree[] children, int id) {
  for each (child in children) {
    match = (child.HasId(id) ? child : SearchTreeForId(child.Children));
    if (match != null) return match;
  }
  return null;
}

// Then...
{
  node = SearchTreeForId(SorcerersCave.theCave.Parties, id);
  if (node != null) generateInterface(...);
}
0
додано
За словами мого професора, мульти-дерево - це структура даних, яку кожен "вузол" тобто. Печера, вечірок, істот і т. д. Можна мати 0 <= x дітей. На відміну від BST, де кожен вузол може мати 0 <= 2 вузла. Ось як він пояснив це принаймні.
додано Автор Dustin E., джерело
Мені жаль, але, на жаль, ні, вимоги до проекту передбачають, що кожен об'єкт повинен бути інстанцією в структурі даних з багатьма деревами, як показано на діаграмі, яку я опублікував
додано Автор Dustin E., джерело
А, бачу. Відзначимо, що інтерфейс Інтерфейсу визначає масив дітей, а не пару дітей. Це характеризує "багатовікове дерево" в термінології вашого професора.
додано Автор Rafe, джерело
Привіт Дастін, я не впевнений, що таке дерево - можливо, колекція дерев? Інтерфейс ITree - це те, що забезпечує цю структуру. У всякому разі, удачі з вашою програмою.
додано Автор Rafe, джерело

оскільки ваша точка входу є об'єктом Cave, можна придумати унікальний рядок, як первинний ключ, який представляє весь об'єкт Cave (Cave, Part, Creatures, Treasures, Artifacts), наприклад, concatination того поля, за допомогою якого ви хочете шукати наприклад якщо ви хочете шукати артефакт за допомогою індексу 3, ви можете зробити рядок як

C-P-C-T/A 

де кожна буква являє собою унікальні індекси в "цьому" класі, і в цьому випадку це може бути схожим

3-4-32-A3 

де 3 - 3-я печера, 4 - 4-а партія ... аж до А3 - артефакт 3-го.

Сподіваюся, що ви знайшли рішення краще, ніж це, якщо просимо поділитися.

0
додано
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників