Java-Gaming.org Hi !
Featured games (91)
games approved by the League of Dukes
Games in Showcase (803)
Games in Android Showcase (237)
games submitted by our members
Games in WIP (867)
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  
  Fast way to filter through data  (Read 14062 times)
0 Members and 1 Guest are viewing this topic.
Offline Ed_RockStarGuy
« Posted 2015-01-26 21:20:09 »

I am looking for a good way to look through a data set and remove all values smaller then for example (50) and bigger then (100), all methods i have tried do not work well when dealing with very large arrays, any suggestions?
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #1 - Posted 2015-01-26 21:27:42 »

What methods have you tried? Simple loop (perhaps split over N threads) is about as good as it gets.
Offline KevinWorkman

« JGO Plugged Duke »


Medals: 288
Projects: 12
Exp: 12 years


HappyCoding.io - Coding Tutorials!


« Reply #2 - Posted 2015-01-26 21:30:12 »

Oh boy, an excuse to use Java 8!

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class Test {
   public static void main(String... args){

      List<Integer> numbers = new ArrayList<Integer>();

      for(int i = 0; i < 10000; i++){
         int n = (int) (Math.random()*150);
         numbers.add(n);
      }

      System.out.println("Unfiltered size:" + numbers.size());

      List<Integer> filteredNumbers =
            numbers.parallelStream()
            .filter(t -> t >= 50 && t <= 100)
            .collect(Collectors.toList());

      System.out.println("Filtered size:" + filteredNumbers.size());
   }
}


Depending on your data, it might also make sense to store it as a sorted data structure, then just remove anything outside of your limits.

You might also consider using a database and letting it do the work for you.

HappyCoding.io - Coding Tutorials!
Happy Coding forum - Come say hello!
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Ed_RockStarGuy
« Reply #3 - Posted 2015-01-26 21:32:07 »

Id love to use a DB but its for the stored chunks in the game, its just to free up some un-used data, but ill give that a shot, ty Smiley
Offline basil_

« JGO Bitwise Duke »


Medals: 418
Exp: 13 years



« Reply #4 - Posted 2015-01-26 21:35:29 »

if you do not care about order :
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
T[] stuff = ...
int size = stuff.length;

for(int i = 0; i < size; i++)
{
  T element = stuff[i];

  if(removeThing(element))
  {
    stuff[i] = stuff[--size];
    stuff[size] = null;

    if(stuff[i] != null) i--;
  }
}

T newstuff[] = new T[size];

System.arraycopy(stuff, 0, newstuff, 0, size);

// newstuff contains what was not removed from stuff.


if order _must_ be kept then things wont be fast. the way ArrayList works :
1  
2  
3  
4  
5  
6  
void removeKeepOrder(int index)
{
  int numMoved = size - index - 1;
  if(numMoved > 0) System.arraycopy(stuff,index + 1,stuff,index,numMoved);
  stuff[--size] = null;
}

but this is slow when you remove items in close to the start.

another somewhat fast way to remove things from a ordered list is to use a doubly-linked-list.
Offline BurntPizza

« JGO Bitwise Duke »


Medals: 486
Exp: 7 years



« Reply #5 - Posted 2015-01-26 21:40:09 »

@Kevin

Unboxed:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
import java.util.Arrays;

public class Test {
   public static void main(String... args) {
     
      int[] numbers = new int[1024];
      int size = 0;
     
      for (int i = 0; i < 10000; i++) {
         int n = (int) (Math.random() * 150);
         
         if (size == numbers.length)
            numbers = Arrays.copyOf(numbers, numbers.length * 2);
         numbers[size++] = n;
      }
     
      System.out.println("Unfiltered size:" + size);
     
      int[] filteredNumbers =
            Arrays.stream(numbers).parallel()
                  .filter(t -> t >= 50 && t <= 100)
                  .toArray();
     
      System.out.println("Filtered size:" + filteredNumbers.length);
   }
}


EDIT: actually doesn't seem that much faster until ~1M elements.
Offline theagentd
« Reply #6 - Posted 2015-01-26 21:42:39 »

If you can cheaply sort the list or the list is already sorted, then it's simply a matter of cutting off all elements after a certain index, which can easily be found using a binary search in the sorted list.

Myomyomyo.
Offline Husk

Senior Devvie


Medals: 20
Exp: 3 years


Want to learn everything.


« Reply #7 - Posted 2015-02-08 11:52:34 »

I hope this thread isn't considered too old to post on, but you might try this:

1  
2  
3  
for (int i = 0; i < numbers.length; i++)
   if (((numbers[i] - lower) & 0xFFFF) <= (upper - lower))
      // numbers[i] is between lower and upper.

You can adjust that as necessary. This yielded a significantly better performance than a simple loop with a check between bounds. The way it works is that it treats numbers - lower as an unsigned number. If the result was negative, it will be perform integer wrapping and go to a higher value than upper - lower will be.

Like BurntPizza has mentioned, splitting this across multiple threads will likely be your biggest performance improvement.

Sorting the array first may be quicker in some cases, depending on what algorithm you use and how sporadic the numbers are in sequence. A quick test using Arrays.sort() on an array with completely arbitrary values yielded significantly worse performance than a simple loop with a check between bounds.

Ideally, you don't want to keep removing elements from the array you have, a huge amount of time will be spent doing that. Instead, if you can, create a second array, and push appropriate numbers in to that one. You can reserve the array size to be the probability of a number being pushed there multiplied by the amount of numbers in your data set.

 Smiley

Offline pitbuller
« Reply #8 - Posted 2015-02-08 12:31:33 »

Sort is O(n log n). Which then enables O(log n) binary search method.
Check bounds is O(n).

It might also be possible to not inserting those values on list all together.


Offline delt0r

JGO Wizard


Medals: 145
Exp: 18 years


Computers can do that?


« Reply #9 - Posted 2015-02-09 13:46:27 »

The quickest way if its already in memory just iterate over the whole thing with an insertion point... this is O(n), you can't do better and this is quite a bit faster than sorting.

For an array... something like this: (probably with some +1 -1 error.... )

1  
2  
3  
4  
5  
6  
7  
8  
int insert=0;
for(int i=0;i<size;i++){
    if(list[i] passes keep test){
        list[insert]=list[i];
        insert++;
    }
}
//set everything from insert+1 to size to some "empty value"

I have no special talents. I am only passionately curious.--Albert Einstein
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Husk

Senior Devvie


Medals: 20
Exp: 3 years


Want to learn everything.


« Reply #10 - Posted 2015-02-09 13:56:24 »

Awesome tip delt0r, I didn't think about that, I'll be sure to use that whenever appropriate.

Pages: [1]
  ignore  |  Print  
 
 

 
Riven (397 views)
2019-09-04 15:33:17

hadezbladez (5280 views)
2018-11-16 13:46:03

hadezbladez (2204 views)
2018-11-16 13:41:33

hadezbladez (5544 views)
2018-11-16 13:35:35

hadezbladez (1150 views)
2018-11-16 13:32:03

EgonOlsen (4584 views)
2018-06-10 19:43:48

EgonOlsen (5462 views)
2018-06-10 19:43:44

EgonOlsen (3119 views)
2018-06-10 19:43:20

DesertCoockie (4015 views)
2018-05-13 18:23:11

nelsongames (4708 views)
2018-04-24 18:15:36
A NON-ideal modular configuration for Eclipse with JavaFX
by philfrei
2019-12-19 19:35:12

Java Gaming Resources
by philfrei
2019-05-14 16:15:13

Deployment and Packaging
by philfrei
2019-05-08 15:15:36

Deployment and Packaging
by philfrei
2019-05-08 15:13:34

Deployment and Packaging
by philfrei
2019-02-17 20:25:53

Deployment and Packaging
by mudlee
2018-08-22 18:09:50

Java Gaming Resources
by gouessej
2018-08-22 08:19:41

Deployment and Packaging
by gouessej
2018-08-22 08:04:08
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!