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:
Efficient general purpose 1D lookup table?

Subject: Efficient general purpose 1D lookup table?

From: paul.domaskis@gmail.com

Date: 6 Dec, 2013 03:12:40

Message: 1 of 8

I have a set of unique integers that map to another set of unique integers. Neither set is necessarily contiguous or monotonic. I would like to implement this as a translation/lookup table. Googling lookup and matlab yields many means of interpolating, but that's not the context I'm working in. I can use ismember to create a translation table, but that uses the index of one array as the value to be translated. It allows me to vectorize the translation of a series of input values, but since the possible input values are not necessarilly contiguous, using the array index does not seem elegant.

Of course, I can write a function that accepts a lookup table in the form of a Nx2 array and simultaneously accepts a vector of input values to translate. My function would loop through each input value, look them up, and return the results (collected into a vector). I was hoping there was a ready-to-use vectorizable way to do this.

Subject: Efficient general purpose 1D lookup table?

From: Eric Sampson

Date: 6 Dec, 2013 16:18:06

Message: 2 of 8

paul.domaskis@gmail.com wrote in message <63a7cd3b-2259-4edc-8ab6-b23b43ba9538@googlegroups.com>...
> I have a set of unique integers that map to another set of unique integers. Neither set is necessarily contiguous or monotonic. I would like to implement this as a translation/lookup table. Googling lookup and matlab yields many means of interpolating, but that's not the context I'm working in. I can use ismember to create a translation table, but that uses the index of one array as the value to be translated. It allows me to vectorize the translation of a series of input values, but since the possible input values are not necessarilly contiguous, using the array index does not seem elegant.
>
> Of course, I can write a function that accepts a lookup table in the form of a Nx2 array and simultaneously accepts a vector of input values to translate. My function would loop through each input value, look them up, and return the results (collected into a vector). I was hoping there was a ready-to-use vectorizable way to do this.

Could you provide a (small, representative) example of two input vectors, and the output that should result from those particular vectors? I'm not sure I follow your description :)

Subject: Efficient general purpose 1D lookup table?

From: Steven Lord

Date: 6 Dec, 2013 16:18:25

Message: 3 of 8


<paul.domaskis@gmail.com> wrote in message
news:63a7cd3b-2259-4edc-8ab6-b23b43ba9538@googlegroups.com...
> I have a set of unique integers that map to another set of unique
> integers. Neither set is necessarily contiguous or monotonic. I would
> like to implement this as a translation/lookup table. Googling lookup and
> matlab yields many means of interpolating, but that's not the context I'm
> working in. I can use ismember to create a translation table, but that
> uses the index of one array as the value to be translated. It allows me
> to vectorize the translation of a series of input values, but since the
> possible input values are not necessarilly contiguous, using the array
> index does not seem elegant.
>
> Of course, I can write a function that accepts a lookup table in the form
> of a Nx2 array and simultaneously accepts a vector of input values to
> translate. My function would loop through each input value, look them up,
> and return the results (collected into a vector). I was hoping there was
> a ready-to-use vectorizable way to do this.

Positive integer values?

locations = 1:10;
values = locations.^2;

interpolationLocations = randi([1 10], 1, 20)
interpolatedValues = values(interpolationLocations)

If some of the first set of unique integers can be large, consider using a
sparse column vector as your table.

values = 0:6
locations = 10.^(values)
lookupTable = sparse(locations, 1, values)

valuesToFind = 10.^randi([0, 6], 20, 1)
foundValues = full(lookupTable(valuesToFind, 1))

You will need to check that none of the elements of valuesToFind are greater
than the number of rows in lookupTable, but that's a fairly quick operation.
And as long as values contains no 0 value (which it does in this case) a
zero in foundValues will correspond to an element in valuesToFind that's not
included in your table.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Efficient general purpose 1D lookup table?

From: paul.domaskis@gmail.com

Date: 6 Dec, 2013 23:37:55

Message: 4 of 8

Eric asked for an example.

Steven wrote:
> locations = 1:10
> values = locations.^2
>
> interpolationLocations = randi([1 10], 1, 20)
> interpolatedValues = values(interpolationLocations)
>
> % If some of the first set of unique integers can be large, consider
> % using a sparse column vector as your table.
>
> values = 0:6
> locations = 10.^(values)
> lookupTable = sparse(locations, 1, values)
>
> valuesToFind = 10.^randi([0, 6], 20, 1)
> foundValues = full(lookupTable(valuesToFind, 1))

Eric, Steven,

Eric:
One example lookup table might be:
   x=unique(randperm(20,10));
   y=randperm(20,10)-10;
   [x' y']

I would be translating any occurance of a value in the left column
into the corresponding value in the right column. I want to the
translation to be vectorizable. The x values are not contiguous, so I
*could* do

   mymap=NaN(1,max(x))
   mymap(x)=y
   % Now do vectorized conversion
   mymap(x(randperm(length(x))))

If I didn't rely on the index of mymap to match the x-value inputs,
then I could have negative values to look up as well.

Steven:
I was in fact using a similar approach as your non-sparse lookup
table. Since the allowable input values are not continguous, it would
be nice if the input argument didn't have to be continuous (matrix
indexes have to be). The sparse matrix approach almost does it, but I
noticed the "full" command, which blows it up into a full matrix. And
it would be good if I could cause some kind of abnormality like use
NaNs in place of the zeros in a sparse matrix.

Currently, I avoid the issue by restricting myself to contigous input
values starting from 1. Strictly speaking, I could encounter
situations where that isn't the case, so I was hoping to write code
that handles those situations without adding to much to the code (and
ideally without departing from vectorization).

Thank you both for your ideas.

Subject: Efficient general purpose 1D lookup table?

From: Steven Lord

Date: 9 Dec, 2013 02:05:23

Message: 5 of 8


<paul.domaskis@gmail.com> wrote in message
news:bbb6e472-db99-423c-a3b2-c3bd5fe29e2e@googlegroups.com...
> Eric asked for an example.
>
> Steven wrote:
>> locations = 1:10
>> values = locations.^2
>>
>> interpolationLocations = randi([1 10], 1, 20)
>> interpolatedValues = values(interpolationLocations)
>>
>> % If some of the first set of unique integers can be large, consider
>> % using a sparse column vector as your table.
>>
>> values = 0:6
>> locations = 10.^(values)
>> lookupTable = sparse(locations, 1, values)
>>
>> valuesToFind = 10.^randi([0, 6], 20, 1)
>> foundValues = full(lookupTable(valuesToFind, 1))
>
> Eric, Steven,
>
> Eric:
> One example lookup table might be:
> x=unique(randperm(20,10));
> y=randperm(20,10)-10;
> [x' y']
>
> I would be translating any occurance of a value in the left column
> into the corresponding value in the right column. I want to the
> translation to be vectorizable. The x values are not contiguous, so I
> *could* do
>
> mymap=NaN(1,max(x))
> mymap(x)=y
> % Now do vectorized conversion
> mymap(x(randperm(length(x))))
>
> If I didn't rely on the index of mymap to match the x-value inputs,
> then I could have negative values to look up as well.
>
> Steven:
> I was in fact using a similar approach as your non-sparse lookup
> table. Since the allowable input values are not continguous, it would
> be nice if the input argument didn't have to be continuous (matrix
> indexes have to be).

I'm not sure what you mean here. In a sparse matrix, only the nonzero
elements are stored. If you have a nonzero element in row 1 and a nonzero
element in row 1000000, that sparse matrix stores just those two nonzero
values.

> The sparse matrix approach almost does it, but I
> noticed the "full" command, which blows it up into a full matrix. And
> it would be good if I could cause some kind of abnormality like use
> NaNs in place of the zeros in a sparse matrix.

The FULL command is just to display the results nicely. It's not necessary
if you want to work with the values.

sparseFoundValues = lookupTable(valuesToFind, 1);
for k = 1:length(interpolationLocations)
    % Do something with interpolationLocations(k) and sparseFoundValues(k)
end
% or just work with the whole vectors
plot(interpolationLocations,sparseFoundValues)


> Currently, I avoid the issue by restricting myself to contigous input
> values starting from 1. Strictly speaking, I could encounter
> situations where that isn't the case, so I was hoping to write code
> that handles those situations without adding to much to the code (and
> ideally without departing from vectorization).
>
> Thank you both for your ideas.


--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Efficient general purpose 1D lookup table?

From: paul.domaskis@gmail.com

Date: 11 Dec, 2013 16:51:16

Message: 6 of 8

On Sunday, December 8, 2013 9:05:23 PM UTC-5, Steven Lord wrote:
><paul.domaskis_AT_gmail.com> wrote:
>> I was in fact using a similar approach as your non-sparse lookup
>> table. Since the allowable input values are not continguous, it
>> would be nice if the input argument didn't have to be continuous
>> (matrix indexes have to be).
>
> I'm not sure what you mean here. In a sparse matrix, only the
> nonzero elements are stored. If you have a nonzero element in row 1
> and a nonzero element in row 1000000, that sparse matrix stores just
> those two nonzero values.

Yes, but you still get a valid return value (zero) when the index points to a zero value. I don't want to have to trap zeros because zero is one of the valid values to be returned in a lookup.

>> ...And it would be
>> good if I could cause some kind of abnormality like use NaNs in
>> place of the zeros in a sparse matrix.
>
> The FULL command is just to display the results nicely. It's not
> necessary if you want to work with the values.
>
> sparseFoundValues = lookupTable(valuesToFind, 1); for k =
> 1:length(interpolationLocations) % Do something with
> interpolationLocations(k) and sparseFoundValues(k) end % or just
> work with the whole vectors
> plot(interpolationLocations,sparseFoundValues)

Understood, thanks. However, it seems to me that I would have to work with full matrix just to stick NaNs into locations where the input argument should be invalid. If I understood correctly.

>> Currently, I avoid the issue by restricting myself to contigous
>> input values starting from 1. Strictly speaking, I could encounter
>> situations where that isn't the case, so I was hoping to write code
>> that handles those situations without adding to much to the code
>> (and ideally without departing from vectorization).

Subject: Efficient general purpose 1D lookup table?

From: Steven Lord

Date: 11 Dec, 2013 18:38:16

Message: 7 of 8


<paul.domaskis@gmail.com> wrote in message
news:b974c596-8d2e-4e2b-96b7-3aa397ae2a6a@googlegroups.com...
> On Sunday, December 8, 2013 9:05:23 PM UTC-5, Steven Lord wrote:
>><paul.domaskis_AT_gmail.com> wrote:
>>> I was in fact using a similar approach as your non-sparse lookup
>>> table. Since the allowable input values are not continguous, it
>>> would be nice if the input argument didn't have to be continuous
>>> (matrix indexes have to be).
>>
>> I'm not sure what you mean here. In a sparse matrix, only the
>> nonzero elements are stored. If you have a nonzero element in row 1
>> and a nonzero element in row 1000000, that sparse matrix stores just
>> those two nonzero values.
>
> Yes, but you still get a valid return value (zero) when the index points
> to a zero value. I don't want to have to trap zeros because zero is one
> of the valid values to be returned in a lookup.

Ah. Yes, that would be a problem. No, it is not possible to say
automatically that the implicitly stored elements in a sparse matrix are
anything other than 0.

>>> ...And it would be
>>> good if I could cause some kind of abnormality like use NaNs in
>>> place of the zeros in a sparse matrix.
>>
>> The FULL command is just to display the results nicely. It's not
>> necessary if you want to work with the values.
>>
>> sparseFoundValues = lookupTable(valuesToFind, 1); for k =
>> 1:length(interpolationLocations) % Do something with
>> interpolationLocations(k) and sparseFoundValues(k) end % or just
>> work with the whole vectors
>> plot(interpolationLocations,sparseFoundValues)
>
> Understood, thanks. However, it seems to me that I would have to work
> with full matrix just to stick NaNs into locations where the input
> argument should be invalid. If I understood correctly.

If NaN is not a valid value, you could try replacing 0 with NaN when you
create the sparse lookup table and replace NaN with 0 (and error on 0) when
looking up values.

>>> Currently, I avoid the issue by restricting myself to contigous
>>> input values starting from 1. Strictly speaking, I could encounter
>>> situations where that isn't the case, so I was hoping to write code
>>> that handles those situations without adding to much to the code
>>> (and ideally without departing from vectorization).

Both the 0 <-> NaN conversions can be vectorized, if you choose that
approach.

--
Steve Lord
slord@mathworks.com
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

Subject: Efficient general purpose 1D lookup table?

From: paul.domaskis@gmail.com

Date: 6 Jan, 2014 16:58:00

Message: 8 of 8

Steven L. wrote:
><paul.d...@gmail.com> wrote:
>>>> ... it would be
>>>> good if I could cause some kind of abnormality like use NaNs in
>>>> place of the zeros in a sparse matrix.

     <...snip...>

>> ...it seems to me that I would have to work
>> with full matrix just to stick NaNs into locations where the input
>> argument should be invalid. If I understood correctly.
>
>If NaN is not a valid value, you could try replacing 0 with NaN when you
>create the sparse lookup table and replace NaN with 0 (and error on 0) when
>looking up values.
>
>>>> Currently, I avoid the issue by restricting myself to contigous
>>>> input values starting from 1. Strictly speaking, I could encounter
>>>> situations where that isn't the case, so I was hoping to write code
>>>> that handles those situations without adding to much to the code
>>>> (and ideally without departing from vectorization).
>
>Both the 0 <-> NaN conversions can be vectorized, if you choose that
>approach.

Unfortunately, 0 is a possible value in the generalization that I'm trying to develop. But thanks for your thoughts.

Tags for this Thread

No tags are associated with 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