collection – GURUnH

Tag: collection

Going through Collection

April 5, 2017 by Hien Nguyen·Comments Off

Year ago, I had a post about iterating through collection. Today my colleague’s question gave me the idea about an example of using collection right. Let’s say we have a collection like NSArray that contains multiple NSString objects, we want to print them in lines includes the line number.

1. Hello
2. Big
3. Big
...
100. World

1. Hello

2. Big

3. Big

...

100. World

Easy problem, right? Let’s see we have some solutions:

NSArray *lines; // with initial content

// #1.
for (NSString *line in lines) {
    int index = [lines indexOfObject:line];
    printf("%d. %@", index, line);
}

// #2.
int index = 0;
for (NSString *line in lines) {
    index++;
    printf("%d. %@", index, line);
}

// #3.
for (int index = 0; index < [lines count]; index++) {
    NSString *line = [lines objectAtIndex:index];
    printf("%d. %@", index + 1, line);
}

NSArray *lines; // with initial content

// #1.

for (NSString *line in lines) {

int index = [lines indexOfObject:line];

printf("%d. %@", index, line);

}

// #2.

int index = 0;

for (NSString *line in lines) {

index++;

printf("%d. %@", index, line);

}

// #3.

for (int index = 0; index < [lines count]; index++) {

NSString *line = [lines objectAtIndex:index];

printf("%d. %@", index + 1, line);

}

What’s a best way? I can say #2 > #3 | #1.

About #3, you can refer to my post to know why we should use iterator instead of index while going through collection. Of course they perform same with NSArray but using iterator help us more easily use another collection type later. So #1 and #2 are usually better than #3. Why is #2 better than #1? The issue is:

/* #1. */ int index = [lines indexOfObject:line];
/* #2. */ index++;

1 2	/* #1. / int index = [lines indexOfObject:line]; / #2. */ index++;

#1 is O(n) while #2 is O(1). We can see #1 is more readable (a bit easier to understand than #2) but #2 has better performance.

You could see #1 is worser in some way. In case of duplicated strings in lines, you may also get wrong result (index is the first found): http://stackoverflow.com/questions/3167849/indexofobject-vs-indexofobjectidenticalto

Iterating through collection

May 25, 2016 by Hien Nguyen·Comments Off

In my opinion, iterating through a collection is very basic and simple thing because it appears in any developer’s code everyday (of course in the languages support collection).

It’s normally my simplest question to start the interview to warmup and make the candidate more confident. But I’m wrong. I’m so surprised that 90% of our candidates, who have been (senior) developers for 2-3 years, cannot give the right answer:

Let say I have a collection LinkedList<int> list. What are differences between 2 types of iterating through list:

for (int i = 0; i < list.length(); i++) {
    int item = list.get(i);
    // do something here...
}

for (int i = 0; i < list.length(); i++) {

int item = list.get(i);

// do something here...

}

and

for (int item : list) {
    // do something here...
}

for (int item : list) {

// do something here...

}

Most of answer I got is “we can have the index by #1 code that we cannot have in #2 code. The performance are the same.”. But it’s incorrect, #1 is really bad code in performance wise.

The performance are the same in the index-based collection, like array or ArrayList. But #1 code is very slow in other collection like LinkedList. The reason is for getting the item at index i (by calling get(i) method), LinkedList needs to iterate from the first item with the counter set to 0, increase it in each step and stop when the counter reach to i. So while the notation of #1 code is O(N²), the notation of #2 code is O(N).

#2 code actually works as

for (Iterator iterator = list.iterator(); iterator.hasNext();) {
    int item = (int)iterator.next();
}

for (Iterator iterator = list.iterator(); iterator.hasNext();) {

int item = (int)iterator.next();

}

#3 code is exactly the way #2 code works before Java introduced for each syntax.

The best solution is always use #2 code for iterating through any collection. If you are worry about the index, another code would be:

int index = 0;
for (int item : list) {
    index++;
    // do something here...
}

int index = 0;

for (int item : list) {

index++;

// do something here...

}

Java is just a used language here but I believe this way works in any language today. Whatever the technology you are chasing, let start from the basic things, language and data structure.

769 total views, no views today