BG Development


Страници: (3) [1] 2 3   ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Обхождане на двойки елементи в LinkedList
Pascal
Публикувано на: 12-05-2017, 17:22
Quote Post



Име:
Група: Потребител
Ранг: Старо куче

Мнения: 679
Регистриран на: 22.11.06



За да го обясня по-бързо, ше го напиша под формата на код:

CODE
for (int i = 0; i < n - 1; i++) {
   for (j = i + 1; j < n; j++) {
       // Perform pair operation to objects[i] and objects[j]
   }
}


С други думи опитвам се да приложа някаква операция на всички двойки обекти, които се подвизават в някаква колекция... Целта ми обаче е да постигна горния ефект с LinkedList в Java

Най-близкото до което се сещам е:
CODE
ListIterator<MyObject> i1 = objects.listIterator();
while (true) {
   MyObject o1 = i1.next();
   if (!i1.hasNext()) break;
   ListIterator<MyObject> i2 = objects.listIterator(i1.nextIndex());
   while (i2.hasNext()) {
       MyObject o2 = i2.next();
       // Perform pair operation to o1 and o2;
   }
}


Основното нещо, което ме дразни в горния код е, че според мен (може и да греша) създаването на нов ListIterator i2 от текущата позиция на i1 е O(n) операция, когато се работи с LinkedList.

Та ... чуденето ми е дали има чалъм да се клонира итератор на LinkedList, без да се налага да се обхожда списъка до текущата позиция на първия итератор?

P.S. Ясно е, че за текущия алгоритъм ArrayList може да е по-подходящ, но аз все пак предпочитам LinkedList по други съображения.

Това мнение е било редактирано от Pascal на 12-05-2017, 17:23
PMEmail Poster
Top
Bender
Публикувано на: 12-05-2017, 17:27
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 4076
Регистриран на: 19.06.14



не може, обаче няма да е зле да кажеш какво искаш да направиш, а не как.


--------------------
Живота е спагети, кода за да работи добре трябва да го наподобява - Дон Реба
...
Живеем в греховни времена, какво очакваш богоугоден и благочестив код ли? - Дон Реба
...
много положителна енергия черпя от вас двамата,единият комунистически девствен,другият яко яхнал асемблерните розови понита - saruman
...
Рано или късно усерите на Виндофс разбират че стоят от неправилната страна на хуя. - ici
PM
Top
Pascal
Публикувано на: 12-05-2017, 17:40
Quote Post



Име:
Група: Потребител
Ранг: Старо куче

Мнения: 679
Регистриран на: 22.11.06



QUOTE (Bender @ 12-05-2017, 17:27)
не може, обаче няма да е зле да кажеш какво искаш да направиш, а не как.

Това е част от проверка за колизии между обекти, която пиша за една малка библиотека за симулация на физически процеси. Като придобие малко по-приличен вид, може и да я публикувам тък.

Просто имам списък с обекти, които си имат позиции в пространството със съответни скорости, ускорения, маси, форми, и пр. и трябва периодично да проверявам за всяка двойка обекти дали са се ударили през последния времеви интервал.

В интерес на истината аз нямам намерение да ползвам Java collections, но в момента пиша прототип, в който за да не си губя времето, ползвам каквото е налично и съм изненадан, че не мога да открия подобно нещо...
PMEmail Poster
Top
FidelDahan
Публикувано на: 12-05-2017, 23:51
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2092
Регистриран на: 12.06.08



Много сложно го мислиш, няма нужда от два итератора, един итератор е достатъчен и имаш само едно обхождане :-)
PMEmail Poster
Top
Pascal
Публикувано на: 13-05-2017, 01:49
Quote Post



Име:
Група: Потребител
Ранг: Старо куче

Мнения: 679
Регистриран на: 22.11.06



QUOTE (FidelDahan @ 12-05-2017, 23:51)
Много сложно го мислиш, няма нужда от два итератора, един итератор е достатъчен и имаш само едно обхождане :-)

Какво имаш предвид?
PMEmail Poster
Top
FidelDahan
Публикувано на: 14-05-2017, 18:57
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2092
Регистриран на: 12.06.08



Нещо такова:

CODE
if (collection.size() < 2) {
 // handle degenerate case
}

Iterator<MyObject> iterator = collection.iterator()

MyObject x = iterator.next()
MyObject y = iterator.next()

while (iterator.hasNext()) {
 // compare x with y
 x = y;
 y = iterator.next()
}

Предполагам, че в този код се крие грешка от тип off by one, но показва подхода само с един итератор.

Това мнение е било редактирано от FidelDahan на 14-05-2017, 18:58
PMEmail Poster
Top
Bender
Публикувано на: 14-05-2017, 19:32
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 4076
Регистриран на: 19.06.14



Може би не ти разбирам примера, но това не е "всяко с всяко"


--------------------
Живота е спагети, кода за да работи добре трябва да го наподобява - Дон Реба
...
Живеем в греховни времена, какво очакваш богоугоден и благочестив код ли? - Дон Реба
...
много положителна енергия черпя от вас двамата,единият комунистически девствен,другият яко яхнал асемблерните розови понита - saruman
...
Рано или късно усерите на Виндофс разбират че стоят от неправилната страна на хуя. - ici
PM
Top
Lachezar
  Публикувано на: 15-05-2017, 11:20
Quote Post



Име: Лъчезар Добрев
Група: Потребител
Ранг: Почетен член

Мнения: 2603
Регистриран на: 10.11.04



Ммм... Така?
CODE
// int n; //
// void check(x, y) // method
IntStream
  .range(0, n * n)
  .parallel()
  .forEach(i -> {
    int x = i % n;
    int y = i / n;
    if (x != y)
      check(x, y);
  });


Корекция: Трябва да го поправя, така ще провери 1 и 2 и отделно 2 и 1, т.е. ще свърши двойна работа.

Това мнение е било редактирано от Lachezar на 15-05-2017, 11:22


--------------------
И'м ватцхинг ъоу...
PMUsers Website
Top
FidelDahan
Публикувано на: 15-05-2017, 11:28
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 2092
Регистриран на: 12.06.08



QUOTE
Може би не ти разбирам примера, но това не е "всяко с всяко"


Прав си, аз май съм разбрал грешно проблема, горния код обработва само за всеки 2 съседни елемента.

QUOTE
Основното нещо, което ме дразни в горния код е, че според мен (може и да греша) създаването на нов ListIterator i2 от текущата позиция на i1 е O(n) операция, когато се работи с LinkedList.


Това е така, да.

QUOTE
Та ... чуденето ми е дали има чалъм да се клонира итератор на LinkedList, без да се налага да се обхожда списъка до текущата позиция на първия итератор?


Евентуално може да пробваш да внедриш собствена имплементация на Iterator, който да има допълнителна функция за клониране.

Един тук предлага алтернатива с 2 итератора, които обаче обхождат от краищата и се срещат по средата. Може би това е по-добро, защото не се усложнява кода със собствени итераторски типове.
http://stackoverflow.com/questions/7758202...terator-in-java

Това мнение е било редактирано от FidelDahan на 15-05-2017, 11:30
PMEmail Poster
Top
Lachezar
Публикувано на: 15-05-2017, 11:48
Quote Post



Име: Лъчезар Добрев
Група: Потребител
Ранг: Почетен член

Мнения: 2603
Регистриран на: 10.11.04



Уф. Разбрах какво имаш предвид.
Може да направиш следното:
Създаваш два итератора, единия за единия елемент, другия за другия елемент.
С единия вървиш само напред, с другия вървиш първо напред до края, после назад до текущия елемент, т.е. с втория итератор правиш зиг-заг напред-назад.
CODE
   public <Z> void run(ListIterator<Z> a, ListIterator<Z> b) {
       if (!a.hasNext() || !b.hasNext())
           return; // Nothing to work with

       boolean// Direction
       d = true; // Forward

       while (a.hasNext()) {
           Z//
           x = a.next();

           if (d) {
               // Reached the end.
               if (!b.hasNext())
                   return;
               b.next();
               while (b.hasNext())
                   check(x, b.next());

               d = !d;
           } else {
               while (b.previousIndex() >= a.nextIndex())
                   check(x, b.previous());
               d = !d;
           }
       }
   }

   <Z> void check(Z x, Z y) {
       // Implement
   }


--------------------
И'м ватцхинг ъоу...
PMUsers Website
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (3) [1] 2 3  Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2015 | BG Development | All Rights Reserved
RSS 2.0