"Shrinking" an array, but keeping original indices results in a small bottleneck

This is a discussion on "Shrinking" an array, but keeping original indices results in a small bottleneck within the C++ Programming forums, part of the General Programming Boards category; Hi! I wrote a piece of code to delete some elements from an array. With deleting I'm saying: replacing the ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    4

    "Shrinking" an array, but keeping original indices results in a small bottleneck

    Hi! I wrote a piece of code to delete some elements from an array. With deleting I'm saying: replacing the original values by 0. I don't know another way to keep the indices of the other elements at the same place. I can't just delete elements by placing them at the end and then creating a new array without the elements at the end, since then I'll end up with different indicies for the elements that I still need.

    So my solution is like this:

    Code:
    //Step #3: Remove old edges from edgeslist and heap
          int aantal = 0;     
          for(edge=0;edge<nbEdges;edge++) { 
            for (i=0; i<nbVertsCells[delVert]; i++) {  
              ver2 = vertsCells[delVert][i];
              if( !fixed2[ver2] && ((EdgesList[edge][0] == delVert) && (EdgesList[edge][1] == ver2)) ) {
                  //Remove old Edges from the edgeslist
                  EdgesList[edge] = new unsigned int[2];
                  EdgesList[edge][0] = 0; //set elements to zero. Adding at the end in the future?
                  EdgesList[edge][1] = 0;
                  delEdge = edge;
                  //Remove old Edges from the Heap
                  heapRemoveEdgeValue(nbEdgesHeap, heapEdges, posEdges, errorCells2, delEdge);
                  delEdgeInd[aantal] = delEdge;
                  aantal++;
                  
              }
            }
          } 
          
             
          //Step #4: Add new edges to edgeslist
          for(i=0;i<nbNewEdges;i++) {
                //EdgesList[delEdgeInd[i]] = new unsigned int[2];
                EdgesList[delEdgeInd[i]][0] = (unsigned int)FinalEdgesList[i][0];
                EdgesList[delEdgeInd[i]][1] = (unsigned int)FinalEdgesList[i][1];
                delete[] FinalEdgesList[i];
          }
          delete[] FinalEdgesList;
    Unfortuantely this piece of code seems to bug a little, when testing it takes VERY long to pass this part. Is there something wrong with my approach? I just put som elements to zero and afterwoods I use these empty place to add new elements into it. Since nbNewEdges is smaller then the amount of zeros created, there'll always be some elements in EdgesList[][] who are still both zero.

    Can anyone help me out with debugging this? There's not really an error or something, but like I said: I think there's a bottleneck in it...
    Last edited by MoGuL; 12-07-2011 at 08:15 AM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    20,968
    This looks like C++ code, so I am moving this thread to the C++ programming forum.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,170
    What is the point of deleting elements if you just set them to 0?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.
    For information on how to enable C++11 on your compiler, look here.
    よく聞くがいい!私は天才だからね! ^_^

  4. #4
    Registered User
    Join Date
    Nov 2011
    Posts
    4
    Quote Originally Posted by Elysia View Post
    What is the point of deleting elements if you just set them to 0?
    In order to distinquish between other elements.. The ones that stay zero, can be disregarded... There will never be a combination of EdgesList[edge][0] and EdgesList[edge][1] both 0 that is valid in the rest of the code...

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    So is this for an edge list based software 3D renderer?

    If so, I can share some code of how to do it the most efficient way. You basically use doubly-intrusive lists, one of which is the deletions list. The nodes themselves actually come from a preallocated buffer, so you have a similar cache performance to what you would with an array.
    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
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,159
    Quote Originally Posted by Elysia View Post
    What is the point of deleting elements if you just set them to 0?
    And what's the point of setting elements to 0 if you're going to delete them?

    If you no longer need to access the element at index 1234 in the array, then... don't access it.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  7. #7
    Registered User
    Join Date
    Nov 2011
    Posts
    4
    Quote Originally Posted by brewbuck View Post
    And what's the point of setting elements to 0 if you're going to delete them?

    If you no longer need to access the element at index 1234 in the array, then... don't access it.
    But how do I keep track of those values then?

    Anyways that wasn't really my question. I just don't understand why the above code seems to fail after a large amount of iterations and thus a large amount of zero elements in my EdgesList.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Put "True results" into different files
    By Coding in forum C++ Programming
    Replies: 5
    Last Post: 12-26-2007, 04:40 PM
  2. help with "shrinking" array
    By believe in forum C Programming
    Replies: 2
    Last Post: 05-11-2007, 12:06 PM
  3. Trouble with OpenGL - "The Incredible Shrinking Magnolias"
    By RossMills in forum Game Programming
    Replies: 4
    Last Post: 11-14-2004, 08:08 AM
  4. "itoa"-"_itoa" , "inp"-"_inp", Why some functions have "
    By L.O.K. in forum Windows Programming
    Replies: 5
    Last Post: 12-08-2002, 07:25 AM
  5. "CWnd"-"HWnd","CBitmap"-"HBitmap"...., What is mean by "
    By L.O.K. in forum Windows Programming
    Replies: 2
    Last Post: 12-04-2002, 06:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21