Thread: How to insert a single value into every array alement?

  1. #1
    Registered User
    Join Date
    Apr 2004
    Posts
    72

    How to insert a single value into every array alement?

    I am currently using this code...

    for (int i = 0; i < m_size; i++)
    m_array[i] = EMPTY_CELL;

    EMPTY_CELL is -666.
    m_array is a dynamic array pointing to an integer.

    Instead of using an O(n) algorithm I'm just wondering if there's a faster way using mem* or other functions? The reason why I'm interested is because EMPTY_CELL is a constant, so it seems like there may be a faster way than having to go through every single element in the array. But even if there was a C/C++ function for this, I can only guess it's O(n) too. But I thought I'd ask anyway so I can lay this idea to rest. Thanks!
    Last edited by philvaira; 08-09-2008 at 05:47 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The built-in C++ vector constructor is also linear on n; and I don't see any way to get something much faster (I don't see much gain in trying to copy 1, then 2, then 4, then ... elements).

  3. #3
    Registered User
    Join Date
    Apr 2004
    Posts
    72
    Alright, thanks!

  4. #4
    Registered User
    Join Date
    Apr 2006
    Posts
    2,149
    There is no way to get better than O(n). The C++ function to do this is fill, which is found in <algorithm>.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Depending on what you're doing, it may make sense to use a vector and resize it to zero items.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    How could you possibly store n values into n slots without performing at least n operations? That would be pure magic.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Well, the line
    Code:
    fread(array, sizeof(array), 1, inFile);
    sure looks like one operation (with array defined properly, etc.) although who knows what it turns into on the machine level.

  8. #8
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    It can be done by copying one sequence of memory with the desired pattern into our array.

    For example if we have an array of 100 pointers and we want to make them null, all we need is to copy 100*4 byte of null bytes to our array. Sure we should have this 400 bytes of sequential null bytes somewhere in memory.

    Think we have an array of
    Code:
    struct student
    {
          char name[80];
          int      mark;
    };
    Then we make an array.
    Code:
    student students[100];
    Students is a sequence of bytes 80 for name 4 for mark, 80 for name 4 for mark.
    If we place a sequence with the same pattern somewhere in memory, for example 80 null bytes plus four bytes for a specific integer (for example zero) and we repeat it 100 times. Then we can fill our students array.

    If we have an array in our program that we want to fill it with predefined values so many times we instantiate an array with those values and copy it to the array we want to fill.

    In short we have to have an image of the array with predefined values and copy it to the array which we want to refresh, initialize, etc
    Last edited by siavoshkc; 08-10-2008 at 12:28 PM.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Quite simple really

    Any loop in your program runs in O(N)
    Any loop hidden inside an API call runs in O(1)

    Obvious really




    If you bought that, I've got a jar of scotch mist for sale.....
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    I'm wading into waters deeper than my ken, since my assembly knowledge is nil, but my rough point was this: say I'm copying 16 shorts in an array. Would that necessarily turn into 16 machine operations (which is what I'm reading brewbuck to claim)? I would think that maybe I would get 8 4-byte copies (or something similar, alignment, etc.). It's still O(n), n/2 is still O(n), but it's not really n operations.

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    *agrees with tabstop*
    Big-O ignores all scale factors, so whether the actual operation is accomplished in N/2 machine operations, or 100*N machine operations, it's still O(N).

    Also, Big-O only works for large (asympotic) values on N on abstract machines.
    Small N on real machines can show very different results.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  12. #12
    System Novice siavoshkc's Avatar
    Join Date
    Jan 2006
    Location
    Tehran
    Posts
    1,246
    mem copy is O(N), but has potential of being much faster than a filler loop in the code.
    Learn C++ (C++ Books, C Books, FAQ, Forum Search)
    Code painter latest version on sourceforge DOWNLOAD NOW!
    Download FSB Data Integrity Tester.
    Siavosh K C

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM
  3. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM
  4. Array Program
    By emmx in forum C Programming
    Replies: 3
    Last Post: 08-31-2003, 12:44 AM
  5. two dimensional dynamic array?
    By ichijoji in forum C++ Programming
    Replies: 6
    Last Post: 04-14-2003, 04:27 PM