current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

Can someone help me optimize speed for my code? I tested it via stopwatch in milliseconds. I've implemented my own ArrayList and I would like to improve its speed without using C# built-in structures.

Mylist.cs

using System;
using System.Collections;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ManualArrayList {
class MyList : IList {
private object[] _items;

public MyList() {
    _items = new object[0];
}

public void PrintElement() {
    for(int i = 0; i < _items.Length; i++) {
        Console.WriteLine(_items[i]);
    }
}

public int Add(object value) {
    object[] tmp = new object[_items.Length + 1];
    for(int i = 0; i < _items.Length; i++) {
        tmp[i] = _items[i];
    }
    tmp[tmp.Length - 1] = value;
    _items = tmp;
    return tmp.Length - 1;
}

public bool Contains(object value) {
    return IndexOf(value) != -1;
}


public int IndexOf(object value) {
    return IndexOf(value, 0);
}

public int IndexOf(object value, int startIndex) {
    for(int i = startIndex; i < _items.Length; i++) {
        if(_items[i].Equals(value)) {
            return i;
        }
    }
    return -1;
}

public void Remove(object value) {
    if(!Contains(value)) {
        return;
    }
    object[] tmp = new object[_items.Length - 1];
    bool deleted = false;
    for(int i = 0, j = 0; i < tmp.Length; i++, j++) {
        if(_items[i].Equals(value) && !deleted) {
            j++;
            deleted = true;
        }
        tmp[i] = _items[j];
    }
    _items = tmp;
}



public void Insert(int index, object value) {
    object[] tmp = new object[_items.Length + 1];
    if(index - 1 >= _items.Length + 1 || index < 0) {
        Console.WriteLine("This type of index was not found in array");
        return;
    }
    for(int i = 0, j = 0; i < tmp.Length && j < _items.Length; i++, j++) {
        if(j == index - 1) {
            tmp[j] = value;
            i++;
        }

        tmp[tmp.Length - 1] = value;
        tmp[i] = _items[j];
    }


    _items = tmp;


}
public void RemoveAt(int index) {
    if(index >= _items.Length || index < 0) {
        Console.WriteLine("This type of index was not found in array");
        return;
    }
    object[] tmp = new object[_items.Length - 1];
    for(int i = 0, j = 0; i < tmp.Length; i++, j++) {
        if(i == index) {
            j++;
        }
        tmp[i] = _items[j];
    }
    _items = tmp;
}


public void Clear() {
    _items = new object[0];
}


public int Count {
    get {
        return _items.Length;
    }
}


// es avxsnat ertad mere...
public object this[int index] {
    get {
        throw new NotImplementedException();
    }
    set {
        throw new NotImplementedException();
    }
}

//es ertad gavaketot
public void CopyTo(Array array, int index) {
    throw new NotImplementedException();
}

//es ertad gavaketot
public IEnumerator GetEnumerator() {
    throw new NotImplementedException();
}

#region We Dont Touch This
public bool IsFixedSize {
    get {
        return false;
    }
}

public bool IsReadOnly {
    get {
        return false;
    }
}

public bool IsSynchronized {
    get {
        return true;
    }
}

public object SyncRoot {
    get {
        return this;
    }
}
#endregion

}
}
share|improve this question
    
I've tested it with stopwatch I mean the speed of code. Here are the results. prntscr.com/a6kvkj – Nikusha Kalatozi 2 days ago
1  
Why are you lying about whether the collection is synchronized? You return true, but this collection is not synchronized. – Eric Lippert yesterday
up vote 4 down vote accepted

First, what meets the eye.

}
#endregion

}
}

The class should be indented under the namespace, and the members of the class should be indented as well; that's why you end the file with same-level closing braces, which is always a sign that something is wrong with the indentation.

I like that your braces are consistent. Typically though, C# code puts the scope-opening brace on the next line - but I'm not into a mood to start a flame war over bracing styles (Java vs. C#), your braces are consistently Java-style, and consistency is good. As a C# developer it's just a bit off-putting, but one gets used to it.

public object this[int index] {
    get {
        throw new NotImplementedException();
    }
    set {
        throw new NotImplementedException();
    }
}

Why not implement the indexer? That NotImplementedException would be rather surprising for someone using your class.. especially since the implementation would be as straightforward as this:

public object this[int index] {
    get {
        return _items[index];
    }
    set {
        _items[index] = value;
    }
}

if(index - 1 >= _items.Length + 1 || index < 0) {
    Console.WriteLine("This type of index was not found in array");
    return;
}

You should definitely be throwing an exception here (an ArgumentException perhaps?). A list that writes to the console sounds very much like mixed responsibilities.

From an API standpoint, it makes no sense to have this member either:

public void PrintElement() {
    for(int i = 0; i < _items.Length; i++) {
        Console.WriteLine(_items[i]);
    }
}

The list itself shouldn't know how to output itself. This member clearly violates the Single Responsibility Principle. Besides, PrintElement being singular it's also misleading - a better name could be PrintContents, or PrintAll, or PrintElements. But it doesn't belong there.

You have a lot of for loops that do the same thing: find the index of an element in the array. You could have that loop written only once, inside IndexOf, and then reuse IndexOf when you need to find the index of an element.

Your list isn't type-safe - it suffers the same problem the .NET 1.1 ArrayList had: it incurs a boxing penalty on value types, ...and this code would be valid:

 var list = new MyList();
 list.Add("foo");
 list.Add(42);
 list.Add(new Something());

You could eliminate this problem the way .NET 2.0 eliminated it: using generics (e.g. implementing IList<T> instead/on top of IList) and working with a T[] instead of an object[].

var list = new MyList<int>();
list.Add("foo");           // won't compile
list.Add(42);              // ok
list.Add(new Something()); // won't compile
share|improve this answer
1  
Just for historical background, in .NET 1.x we got around the type safety issue by inheriting from CollectionBase, the abstract core of ArrayList and overriding all of the methods with type specific versions (e.g. Add(object o) becomes Add(FizzBuzz fb), and so on). – Zack yesterday
    
@Zack Interesting. AFAICT that still incurred a boxing penalty though, the strongly-typed façade was really just that: a façade. Under the hood it was all object anyway. – Mat's Mug♦ yesterday
    
@Mat'sMug Thank you for such a detailed explanation, I really appreciated your work sir. It really helped me so much to understand so minimal problems with myself. – Nikusha Kalatozi yesterday
1  
@Mat's Mug It did. I was just sharing it as potentially interesting historical trivia with regards to type safety for how things used to be. – Zack yesterday
up vote 6 down vote

Probably the best improvement would be to allocate extra storage space and also store how many elements your list contains. Right now you allocate a new array and copy all existing values on each add operation, and this results in O(n) time complexity for adding items. Instead you could increase inner array twice each time, this would result in amortized O(1). Also, with this approach you wouldn't need to allocate new arrays on removal operations, as you could just leave empty space at the end.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.