Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
priority queue - matlab/java implementation?

Subject: priority queue - matlab/java implementation?

From: gg

Date: 8 Oct, 2010 15:08:04

Message: 1 of 4

Dear All,

I am looking for a good data structure to implement certain operation and then for the optimal implementation (or a good way of doing this) in Matlab.

What I want to do:
I have a large number of things, for example as an array of structs. To each of those things is associated a property or field "value", which is a positive double. The operations I would like to support with my data structure are (in this sequence)

1. get the thing or the things with the largest value
2. remove the thing(s) with the largest value
3. add (as in "include") new things with different values to the data structure.

As I have a great number of these things and will run through 1.-3. very often, I need an efficient implementation. For example the obvious solution: sorting the struct, polling the first element, removing it and catenating the new elements at the end is inefficient due to the repeated sorting.
 
From what I saw so far, a priority queue seems to be what I need.

My concrete question is now How can I implement this in Matlab?

1. File Exchange:
There is an implementation by Andrea Tagliasacchi on the file exchange but this is done MEX/C++, which is something I have never done before.
2. JAVA
Apparently there is a queue implementation in Java. The problem with this is, I need to retrieve not only the value itself but

also an index or pointer to the thing the value is associated with. I am not sure how to do this in Java. Is it possible to

define [value, index] pairs together with a custom comparator within Matlab and passing this to Java?

3. Other solutions?

Any ideas and help would be gratly appreciated.

Regards,
gg

Subject: priority queue - matlab/java implementation?

From: Yair Altman

Date: 9 Oct, 2010 16:43:05

Message: 2 of 4

"gg" <guido.dot.gruetzner@secquaero.dot.com> wrote in message <i8nc4k$f0u$1@fred.mathworks.com>...
> Dear All,
>
> I am looking for a good data structure to implement certain operation and then for the optimal implementation (or a good way of doing this) in Matlab.
>
> What I want to do:
> I have a large number of things, for example as an array of structs. To each of those things is associated a property or field "value", which is a positive double. The operations I would like to support with my data structure are (in this sequence)
>
> 1. get the thing or the things with the largest value
> 2. remove the thing(s) with the largest value
> 3. add (as in "include") new things with different values to the data structure.
>
> As I have a great number of these things and will run through 1.-3. very often, I need an efficient implementation. For example the obvious solution: sorting the struct, polling the first element, removing it and catenating the new elements at the end is inefficient due to the repeated sorting.
>
> From what I saw so far, a priority queue seems to be what I need.
>
> My concrete question is now How can I implement this in Matlab?
>
> 1. File Exchange:
> There is an implementation by Andrea Tagliasacchi on the file exchange but this is done MEX/C++, which is something I have never done before.
> 2. JAVA
> Apparently there is a queue implementation in Java. The problem with this is, I need to retrieve not only the value itself but
>
> also an index or pointer to the thing the value is associated with. I am not sure how to do this in Java. Is it possible to
>
> define [value, index] pairs together with a custom comparator within Matlab and passing this to Java?
>
> 3. Other solutions?
>
> Any ideas and help would be gratly appreciated.
>
> Regards,
> gg


Look at Java's standard PriorityQueue class (available since Java 1.5, which is pre-bundled in all Matlab releases since 7.0.4 = R14SP2):

http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html
http://www.javaclass.info/generics/queue/priority-queue.php
http://stackoverflow.com/questions/683041/java-how-do-i-use-a-priorityqueue

In Matlab:
>> q=java.util.PriorityQueue;
>> q.add({value,index});

Yair Altman
http://UndocumentedMatlab.com

Subject: priority queue - matlab/java implementation?

From: gg

Date: 11 Oct, 2010 07:10:05

Message: 3 of 4

Dear Yair,

thank you for the comment. This is exactly what I am trying to do. I am stuck with the issue of defining a custom Comparator though. I need this custom Comparator as the elements of the queue are not elementary types (they are value index pairs). So my question boils down to: Can I define somehow a Java Comparator within the Matlab environment or would I need to define a new Java Object and accordingly use a java compiler or something similar?

I find in the documentation (Quote):
Sources of Java Classes

Following are Java class sources that you can use in the MATLAB workspace:

    * Java built-in classes — general-purpose class packages, such as java.util, included in the Java language. See your Java language documentation for descriptions of these packages.
    * Third-party classes — packages of special-purpose Java classes.

    * User-defined classes — Java classes or subclasses of existing classes that you define. You need to use a Java language development environment to do this, as explained in the following section.
(End of quote)

So I understand that a PriorityQueue would be of the first type but the Comparator object of the third kind. Is that true?

Regards and thanks again
Guido

"gg" <guido.dot.gruetzner@secquaero.dot.com> wrote in message <i8nc4k$f0u$1@fred.mathworks.com>...
> Dear All,
>
> I am looking for a good data structure to implement certain operation and then for the optimal implementation (or a good way of doing this) in Matlab.

Subject: priority queue - matlab/java implementation?

From: Yair Altman

Date: 11 Oct, 2010 07:51:03

Message: 4 of 4

"gg" <guido.dot.gruetzner@secquaero.dot.com> wrote in message <i8ud8d$qji$1@fred.mathworks.com>...
> Dear Yair,
>
> thank you for the comment. This is exactly what I am trying to do. I am stuck with the issue of defining a custom Comparator though. I need this custom Comparator as the elements of the queue are not elementary types (they are value index pairs). So my question boils down to: Can I define somehow a Java Comparator within the Matlab environment or would I need to define a new Java Object and accordingly use a java compiler or something similar?
>
> I find in the documentation (Quote):
> Sources of Java Classes
>
> Following are Java class sources that you can use in the MATLAB workspace:
>
> * Java built-in classes — general-purpose class packages, such as java.util, included in the Java language. See your Java language documentation for descriptions of these packages.
> * Third-party classes — packages of special-purpose Java classes.
>
> * User-defined classes — Java classes or subclasses of existing classes that you define. You need to use a Java language development environment to do this, as explained in the following section.
> (End of quote)
>
> So I understand that a PriorityQueue would be of the first type but the Comparator object of the third kind. Is that true?
>
> Regards and thanks again
> Guido
>
> "gg" <guido.dot.gruetzner@secquaero.dot.com> wrote in message <i8nc4k$f0u$1@fred.mathworks.com>...
> > Dear All,
> >
> > I am looking for a good data structure to implement certain operation and then for the optimal implementation (or a good way of doing this) in Matlab.


Correct. The comparator in your case would be relatively simple since your data is a simple array type - Matlab's {a,b} convert into a simple Java Object[] array consisting of a,b.

Yair Altman
http://UndocumentedMatlab.com

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us