Results 1 to 11 of 11

Thread: Array

  1. #1
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

    Default Array

    I need to make an array using primitive array so I cannot use the class ArrayList.

    At the moment I initialise my array as follows:

    array = new new String[100];

    But my array will need to hold hundreds of thousands of strings, so is there a way I can make the array of maximum size? Or, to expand its size each time a new word is added?

  2. #2
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,450
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ile4 View Post
    I need to make an array using primitive array so I cannot use the class ArrayList.

    At the moment I initialise my array as follows:

    array = new new String[100];

    But my array will need to hold hundreds of thousands of strings, so is there a way I can make the array of maximum size? Or, to expand its size each time a new word is added?
    If you're not allowed to use an ArrayList you have to mimic its behaviour: you have to keep track of the number of elements in your array as well as the size of the array; when a new elements needs to be inserted and the array is full, allocate another (larger) array and copy everything over from the old array to the new array; now you can store the new element. How much larger the new array is going to be is crucial: you don't want to waste a lot of memory but you don't want to allocate a new array for every new item to be inserted.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  3. #3
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

    Default

    I see what you mean, but the algorithm we use needs to work in nlogn time so wouldnt this be quite slow to make a new array and copy everything over? Would this run in nlogn time or better?

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,450
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ile4 View Post
    I see what you mean, but the algorithm we use needs to work in nlogn time so wouldnt this be quite slow to make a new array and copy everything over? Would this run in nlogn time or better?
    Copying an array over to another array takes O(n) steps when the length of the array is n and n < n*log(n). ArrayLists add n/2 elements to the new array, do your math ;-)

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

    Default

    Hmm i don't know what O(n) means i am really new to programming. and i am not very good at maths, for small numbers isnt n > nlogn? So what time format will this work in? :confused:

  6. #6
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,450
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ile4 View Post
    Hmm i don't know what O(n) means i am really new to programming. and i am not very good at maths, for small numbers isnt n > nlogn? So what time format will this work in? :confused:
    Nope, n < n*log(n); (divide both the left and right sides by n) 1 < log(n); so if we use the 2log( ... ) if n > 2 the relation is true. In your case n is much larger than 2.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  7. #7
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

    Default

    Ah okay, I don't know how to go about coding that. At the moment I have this:

    Java Code:
    public class MyArray {
        
        private String[] array;
        private int maximum = 10;
        
        public Anagrams () {
            array = new String[maximum];
        }
        
        public void add(String word) {
            for (int i = 0; i < maximum; i++) {
                if (array[i] == null) {
                    array[i] = word;
                    max++; 
                    break;                
                }
            }
        }
    So in my for loop would I need to create a new array of size max + 1 (because your adding one word at a time). But how would I go about copying all the words from my old array over to my new array?

  8. #8
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,450
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ile4 View Post
    Ah okay, I don't know how to go about coding that. At the moment I have this:

    Java Code:
    public class MyArray {
        
        private String[] array;
        private int maximum = 10;
        
        public Anagrams () {
            array = new String[maximum];
        }
        
        public void add(String word) {
            for (int i = 0; i < maximum; i++) {
                if (array[i] == null) {
                    array[i] = word;
                    max++; 
                    break;                
                }
            }
        }
    So in my for loop would I need to create a new array of size max + 1 (because your adding one word at a time). But how would I go about copying all the words from my old array over to my new array?
    Don´t do it like that; fill your array starting from the first element. You should keep track where the first unused element is. If the index of that element equals the size of the entire array, a new array should be allocated and the content of the old array should be copied to the new array. Something like this:

    Java Code:
    int free= 0; // the first free element
    int[] array= new int[SOME_VALUE]; // the array 
    ...
    void add(int element) {
       if (free == array.length) // this array is full
          newArray(); // create a larger one
       array[free++]= element;
    }
    Now you have to write the newArray() method.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  9. #9
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

    Default

    Thank you for all your help so far, I have written the code. It is now creating a new array each time a new element needs to be added, so it starts off with length 0, then i add a new element and the size is 1, but when i add a second element the size is 2, the second element is in space 2 (well 1) but the first element is gone. So it the code is working how I want it to but in my newArray() method I need to clone the array and I cant figure out how I would do this.
    I thought of storing all the elements in a field and then copying them over but the only field that can store multiple values is an array...! So how can I copy the current elements of an array over to a new array?

  10. #10
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,450
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by ile4 View Post
    Thank you for all your help so far, I have written the code. It is now creating a new array each time a new element needs to be added, so it starts off with length 0, then i add a new element and the size is 1, but when i add a second element the size is 2, the second element is in space 2 (well 1) but the first element is gone. So it the code is working how I want it to but in my newArray() method I need to clone the array and I cant figure out how I would do this.
    I thought of storing all the elements in a field and then copying them over but the only field that can store multiple values is an array...! So how can I copy the current elements of an array over to a new array?
    For the copying business have a look at the Arrays class or the System class. Both classes have methods for copying entire arrays. Also, if the array is full don't create an array with just room for one more element; that is extremely expensive; I'd create a new array of length 3*n/2 where n is the length of the original array.

    kind regards,

    Jos
    cenosillicaphobia: the fear for an empty beer glass

  11. #11
    ile4 is offline Member
    Join Date
    Nov 2010
    Posts
    24
    Rep Power
    0

Similar Threads

  1. Replies: 23
    Last Post: 09-07-2010, 08:12 PM
  2. Replies: 2
    Last Post: 09-06-2010, 01:03 AM
  3. create a 2d char array from a 1D string array
    By jschmall12 in forum New To Java
    Replies: 1
    Last Post: 04-27-2010, 09:01 PM
  4. Array length and printing out uninitialized array.
    By nicolek808 in forum New To Java
    Replies: 4
    Last Post: 09-10-2009, 09:12 AM
  5. Replies: 1
    Last Post: 03-31-2009, 06:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •