Get Index of Array Element Faster Than O(N)

Get index of array element faster than O(n)

Convert the array into a hash. Then look for the key.

array = ['a', 'b', 'c']
hash = Hash[array.map.with_index.to_a]    # => {"a"=>0, "b"=>1, "c"=>2}
hash['b'] # => 1

What is the fast way of getting an index of an element in an array?

As long as there is no knowledge about the array (is it sorted? ascending or descending? etc etc), there is no way of finding an element without inspecting each one.

Also, that is exactly what indexOf does (when using lists).

In C, accessing my array index is faster or accessing by pointer is faster?

templatetypedef has summed it up. To add some support to his response. Take these example functions:

unsigned int fun1 ( unsigned int *x )
{
    unsigned int ra,rb;

    rb=0;
    for(ra=0;ra<1000;ra++) rb+=*x++;
    return(rb);
}

unsigned int fun2 ( unsigned int *x )
{
    unsigned int ra,rb;
    rb=0;
    for(ra=0;ra<1000;ra++) rb+=x[ra];
    return(rb);
}

Now gcc produced this:

00000000 fun1:
   0:   e52d4004    push    {r4}        ; (str r4, [sp, #-4]!)
   4:   e1a03000    mov r3, r0
   8:   e2804efa    add r4, r0, #4000   ; 0xfa0
   c:   e3a00000    mov r0, #0
  10:   e1a02003    mov r2, r3
  14:   e492c004    ldr ip, [r2], #4
  18:   e5931004    ldr r1, [r3, #4]
  1c:   e2823004    add r3, r2, #4
  20:   e080000c    add r0, r0, ip
  24:   e1530004    cmp r3, r4
  28:   e0800001    add r0, r0, r1
  2c:   1afffff7    bne 10 
  30:   e49d4004    pop {r4}        ; (ldr r4, [sp], #4)
  34:   e12fff1e    bx  lr

00000038 fun2:
  38:   e3a03000    mov r3, #0
  3c:   e1a02003    mov r2, r3
  40:   e790c003    ldr ip, [r0, r3]
  44:   e2833004    add r3, r3, #4
  48:   e7901003    ldr r1, [r0, r3]
  4c:   e2833004    add r3, r3, #4
  50:   e082200c    add r2, r2, ip
  54:   e3530efa    cmp r3, #4000   ; 0xfa0
  58:   e0822001    add r2, r2, r1
  5c:   1afffff7    bne 40 
  60:   e1a00002    mov r0, r2
  64:   e12fff1e    bx  lr

The code is different, but I am surprised at the missed opportunities for optimization.

Clang/llvm produced this:

00000000 fun1:
   0:   e3a01000    mov r1, #0
   4:   e3a02ffa    mov r2, #1000   ; 0x3e8
   8:   e1a03001    mov r3, r1
   c:   e2522001    subs    r2, r2, #1
  10:   e490c004    ldr ip, [r0], #4
  14:   e08c3003    add r3, ip, r3
  18:   e2c11000    sbc r1, r1, #0
  1c:   e182c001    orr ip, r2, r1
  20:   e35c0000    cmp ip, #0
  24:   1afffff8    bne c 
  28:   e1a00003    mov r0, r3
  2c:   e12fff1e    bx  lr

00000030 fun2:
  30:   e3a01000    mov r1, #0
  34:   e3a02ffa    mov r2, #1000   ; 0x3e8
  38:   e1a03001    mov r3, r1
  3c:   e2522001    subs    r2, r2, #1
  40:   e490c004    ldr ip, [r0], #4
  44:   e08c3003    add r3, ip, r3
  48:   e2c11000    sbc r1, r1, #0
  4c:   e182c001    orr ip, r2, r1
  50:   e35c0000    cmp ip, #0
  54:   1afffff8    bne 3c
  58:   e1a00003    mov r0, r3
  5c:   e12fff1e    bx  lr

You might notice that the compiler produced the exact same code, pointer or offset. And by changing compilers I was better off than changing pointer vs array indexing. I think llvm could have done a little better, I will need study this some more to understand what my code did to cause this.

EDIT:

I was hoping to get the compiler to at a minimum use the ldr rd,[rs],#4 instruction which favors pointers, and hoped the compiler would see that it could destroy the array address thus treating it like a pointer rather than an offset into an array (and use the above instruction, which is basically what clang/llvm did). Or if it did the array thing that it would use the ldr rd,[rm,rn] instruction. Basically was hoping one of the compilers would generate one of these solutions:

funa:
    mov r1,#0
    mov r2,#1000
funa_loop:
    ldr r3,[r0],#4
    add r1,r1,r3
    subs r2,r2,#1
    bne funa_loop
    mov r0,r1
    bx lr

funb:
    mov r1,#0
    mov r2,#0
funb_loop:
    ldr r3,[r0,r2]
    add r1,r1,r3
    add r2,r2,#4
    cmp r2,#0x4000
    bne funb_loop
    mov r0,r1
    bx lr

func:
    mov r1,#0
    mov r2,#4000
    subs r2,r2,#4
func_loop:
    beq func_done
    ldr r3,[r0,r2]
    add r1,r1,r3
    subs r2,r2,#4
    b func_loop
func_done:
    mov r0,r1
    bx lr

Didnt quite get there but got pretty close. This was a fun exercise. Note the above is all ARM assembler.

In general, (not my specific C code example and not necessarily an ARM), a number of the popular architectures you will have a load from a register based address (ldr r0,[r1]) and a load with a register index/offset (ldr r0,[r1,r2]) where the address is the sum of the two registers. one register ideally is the base address of the array and the second the index/offset. The former load from register lends itself to pointers, the latter to arrays. if your C program is NOT going to change or move the pointer or index, then in both cases that means a static address which is computed then a normal load is used, both array and pointer should produce the same instructions. For the more interesting case of changing the pointer/index.

Pointer

ldr r0,[r1]
...
add r1,r1,some number

Array index

ldr r0,[r1,r2]
...
add r2,r2,some number

(replace the load with a store and the add with a sub as needed)

Some architectures do not have a three register register index instruction so there you have to do something like

array index:
mov r2,r1
...
ldr r0,[r2]
...
add r2,r2,some number

Or depending on the compiler it can get really bad, esp if you compile for debugging or without optimizations, and assuming you dont have a three register add

array index:
mov r2,#0
...
mov r3,r1
add r3,r2
ldr r4,[r3]
...
add r2,some number

So it is quite possible that the two approaches are equal. As seen on the ARM, it can combine the two (within limits for the immediate) pointer instructions into one, making that a little faster. The array index solution burns more registers, and depending on the number of available registers for the architecture that pushes you toward having to swap registers out to the stack sooner and more often (than you would with pointers), slowing you down even more. If you dont mind destroying the base address, the bottom line is the pointer solution might give you an advantage from a performance perspective. It has a lot to do with your code and the compiler. For me it readability comes into play and I feel arrays are easier to read and follow, and second do I need to preserve that pointer to free a malloc or to go through that memory again, etc. If so I will probably use an array with an index, if it is a one time pass and I dont care about destroying the base address I will use a pointer. As you saw above with the compiler generated code, if performance is critical, then hand code the solution in assembler anyway (based on suggested approaches by letting the compilers try it first).

Is there a way to get the last element of a list faster than O(n) in Java?

list.get(list.size()-1) would always be O(n) because a linked list is not a random access data structure like a primitive array. To retrieve a value of a given position in the list, you would have to traverse the list starting at the first node until you get to the node of the position you want. So, don't use list.get(index) to retrieve the last element. Many implementation maintain a reference to the last node in the list so that retrieving the last element is O(1). I don't have the code of java.util.LinkedList but I would imagine its method getLast() is O(1).

In an array of objects, fastest way to find the index of an object whose attributes match a search

Maybe you would like to use higher-order functions such as "map".
Assuming you want search by 'field' attribute:

var elementPos = array.map(function(x) {return x.id; }).indexOf(idYourAreLookingFor);
var objectFound = array[elementPos];

Is the Set.has() method O(1) and Array.indexOf O(n)?

If one read the specification of has(), there is an algorithm describing it:

Algorithm for Set.prototype.has(value):

The following steps are taken:

• Let S be the this value.
• If Type(S) is not Object, throw a TypeError exception.
• If S does not have a [[SetData]] internal slot, throw a TypeError exception.
• Let entries be the List that is the value of S’s [[SetData]] internal slot.
• Repeat for each e that is an element of entries,
  
  
  • If e is not empty and SameValueZero(e, value) is true, return true.
• Return false.

And apparently, based on that algorithm and the presence of the word REPEAT one can have some confusion about it to be O(1) (we could think it could be O(n)). However, on the specification we can read that:

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

Thanks to @CertainPerformance for pointing this.

So, we can create a test to compare Array.indexOf() and Set.has() in the worst case, i.e. look for an item that isn't in the array at all (thanks to @aquinas for pointing this test):

// Initialize array.let a = [];
for (let i = 1; i < 500; i++){    a.push(i);}
// Initialize set.let s = new Set(a);
// Initialize object.let o = {};a.forEach(x => o[x] = true);
// Test Array.indexOf().console.time("Test_Array.indexOf()");for (let i = 0; i <= 10000000; i++){    a.indexOf(1000);}console.timeEnd("Test_Array.indexOf()");
// Test Set.has().console.time("Test_Set.has()");for (let i = 0; i <= 10000000; i++){    s.has(1000);}console.timeEnd("Test_Set.has()");
// Test Object.hasOwnProperty().console.time("Test_Object.hasOwnProperty()");for (let i = 0; i <= 10000000; i++){    o.hasOwnProperty(1000);}console.timeEnd("Test_Object.hasOwnProperty()");

.as-console {background-color:black !important; color:lime;}.as-console-wrapper {max-height:100% !important; top:0;}