Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (577)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Systematic removal from a LinkedList  (Read 1221 times)
0 Members and 1 Guest are viewing this topic.
Offline Joshua Waring
« Posted 2012-11-11 10:10:29 »

I'm trying to remove items from a linked list and only going through the list once so I came up with a method of doing so.
But the numbers removed aren't the correct values. which are removed :/ and I don't know why (the first one is removed correctly)
could someone please locate the logic error?
http://www.java-gaming.org/?action=pastebin&id=306

The purpose of this is to make more efficient culling in my particle system Smiley

The world is big, so learn it in small bytes.
Offline princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #1 - Posted 2012-11-11 10:56:04 »

 Cranky

Cas Smiley

Offline Danny02
« Reply #2 - Posted 2012-11-11 10:57:44 »

yea,h it's probably a bad idea to use a linkedlist for particle effects
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline matheus23

JGO Kernel


Medals: 109
Projects: 3


You think about my Avatar right now!


« Reply #3 - Posted 2012-11-11 10:58:16 »

Cranky

Cas Smiley

~33.3% Smiley madness...

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2012-11-11 10:59:09 »

I'm happy even when I'm cranky.

http://www.java-gaming.org/topics/arraylist-vs-linkedlist/26572/view.html

Cas Smiley

Offline Joshua Waring
« Reply #5 - Posted 2012-11-11 11:56:48 »

But an array list has all that array resizing.

The world is big, so learn it in small bytes.
Offline matheus23

JGO Kernel


Medals: 109
Projects: 3


You think about my Avatar right now!


« Reply #6 - Posted 2012-11-11 11:59:12 »

If you like none of those, try the GapList, which is supposed to be a very fast list, and I have made good experience with this kind of list.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Cero
« Reply #7 - Posted 2012-11-11 13:04:36 »

you can also just use an array with a simple max fixed size I guess

Offline Joshua Waring
« Reply #8 - Posted 2012-11-11 13:18:12 »

Nah, it has to be dynamic, Could you use a buffer of objects instead?

The world is big, so learn it in small bytes.
Online theagentd
« Reply #9 - Posted 2012-11-11 15:04:01 »

Nah, it has to be dynamic, Could you use a buffer of objects instead?
http://www.java-gaming.org/topics/arraylist-hashtable-or-for-holding-in-game-objects/25388/msg/219160/view.html#msg219160

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 404
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #10 - Posted 2012-11-11 17:19:31 »

Why is it that array resizing is reckoned to be slow?

(Starter hint: it's not, it's blazingly, blazingly fast)

Cas Smiley

Offline Joshua Waring
« Reply #11 - Posted 2012-11-11 23:12:45 »

But I'd like to do a lot of remove calls at once sometimes hitting about 70K per update.
Right now I use an array of particles which onced culled are moved to a recyclearray to be reset an reused once you spawn more. If they're useable you don't create more and just recycle. I was thinking maybe just having one array and two intbuffer each with indexes to particles one being active and one being flagged. So instead of cycling through the array I can go through the indexes and culling of a particle becomes just moving an int from one buffer to another.

The world is big, so learn it in small bytes.
Online theagentd
« Reply #12 - Posted 2012-11-12 00:56:53 »

But I'd like to do a lot of remove calls at once sometimes hitting about 70K per update.
Right now I use an array of particles which onced culled are moved to a recyclearray to be reset an reused once you spawn more. If they're useable you don't create more and just recycle. I was thinking maybe just having one array and two intbuffer each with indexes to particles one being active and one being flagged. So instead of cycling through the array I can go through the indexes and culling of a particle becomes just moving an int from one buffer to another.
That wouldn't preserve the ordering of the particles, which might look weird at times, since you would never be able to know if new particles would spawn above or under the particles already existing. It might also be really slow since you're completely screwing up the CPU's cache due to your random access pattern.

Myomyomyo.
Offline Joshua Waring
« Reply #13 - Posted 2012-11-12 02:50:01 »

I was actually about to write a benchmark and create an ArrayList and measure how long it takes to go through n1 to n1million and compair it to rnaodmly picking one million.
Let's see how that goes.

The world is big, so learn it in small bytes.
Offline Joshua Waring
« Reply #14 - Posted 2012-11-12 04:00:40 »

Something rather interesting happened with the speed of the two as the about of tests increased by 10* ( the percent is how much faster sequential is compaired to random
Cycles              Percent
1                         198%
10                       194%
100                     190%
1000                   188%
10000                 186%
100000               155%
1000000             118%
10000000           104%
100000000         88%
1000000000       89%

They always teach you in science class to increase your sample size to 'increase data reliability' but this has broken that... it's 2x faster with little cycles and slower with a lot. as you can assume sitting there while it did a 2x One billion cycles of a million searches took a long time.

The world is big, so learn it in small bytes.
Offline StumpyStrust
« Reply #15 - Posted 2012-11-12 05:39:55 »

...after my data structures calls I learn a few things. One: never listen to the advice from that particular professor....ever. Two: Stick to arrays/ArrayList for just about everything.

Offline Roquen
« Reply #16 - Posted 2012-11-12 07:06:26 »

Understanding the impact of memory access, none vs linear memory vs (statistically) random is very important in modern CPUs...by modern here I don't mean that any of this is new.  You'll still hear people talking about the classic "time vs. space" trade-off which is more or less BS in common cases.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (49 views)
2014-10-17 03:59:02

Norakomi (38 views)
2014-10-16 15:22:06

Norakomi (31 views)
2014-10-16 15:20:20

lcass (34 views)
2014-10-15 16:18:58

TehJavaDev (65 views)
2014-10-14 00:39:48

TehJavaDev (65 views)
2014-10-14 00:35:47

TehJavaDev (54 views)
2014-10-14 00:32:37

BurntPizza (72 views)
2014-10-11 23:24:42

BurntPizza (43 views)
2014-10-11 23:10:45

BurntPizza (84 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!