deleting elements in an array... - Tilted Forum Project Discussion Community

cheerios · 01-22-2004, 07:04 PM

Ok, I'm working on my algorithms homework, and I come across this problem:

Quote:

Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array's size n.
a. Delete the ith element of an array(1<=i<=n).
b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course.)

now, I'm honestly baffled and the chapter has nothing to say about array element deletion. Because in Data Structures they tought us that array's downside was that they were slow to delete and insert into the middle of the array, because a new array had to be created, and every value had to be copied in, with the correct value added or left out. now, this question implies that is not true, and I have no clue how that could be. Any hints?

kel · 01-22-2004, 07:28 PM

You mean a regular array, as in the C++ declaration

Code:

int x[100];

?

You don't normally delete elements from an array.
I don't know of any data structure that supports deletion in O(1) time.

I mean a hash table can do that if the set of keys is the same size as the potential set of elements. But that isn't much different then deleting from a regular array.

cheerios · 01-22-2004, 07:41 PM

yeah, i mean a regular array. that's why this has me baffled. 'cuz you don't delete out of an array 'cuz it's a waste of time!

sailor · 01-22-2004, 08:39 PM

Ha, there was a CS major explaining this to someone in the library this afternoon. I didnt join in because I dont know much about programming, but IIRC, she said just what you did--you cant really delete them, you have to make a new array minus the element you wish to delete, or, if you can, just set the element equal to null.

kel · 01-22-2004, 08:56 PM

Creating a new array and copying is an O(n) operation so that can't be it. Arrays don't have null values, unless they are arrays of pointers, which isn't specified.

Question = nonsensical.

hlprmnky · 01-23-2004, 07:06 AM

Well, I agree that the question doesn't seem to make a lot of sense.

The closest thing I can come to that's a "real" answer (i.e., not just 'set the array element to null') is this:

for(j = i; j < array.length - 1; j++) {
array[j] = array[j + 1];
}
array[array.length] = null;

Although in a worst-case analysis this is in fact O(n), it doesn't depend directly on the length of the array in the same way that copying all the elements does.

Be sure to let us know what the answer is!

The_Dude · 01-23-2004, 09:08 AM

i'm thinking hash tables here.

the actual table being a linked list which keeps track of the previous and the next elements.

if the hash table is organized by element #, then u should be able to go into x element and remove it.

same thing with the b part.

cheerios · 01-23-2004, 01:12 PM

well, I went in to ask, but our department is going through acredditation this semester and the entire dept is out for meetings the whole day.

I am NOT amused. So, your (and my) answer will have to wait until monday.

Yakk · 01-23-2004, 01:51 PM

Code:

void delete_ith(element_type* array, int* array_length, int i) {
  array[i] = array[*array_length-1];
  *array_length = *array_length-1;
}

Shortens the "length" of the array by one, deleting the ith element.

The actual memory allocated to the array might be the same, but 1 less element is used, and the ith element has been deleted/overwritten.

Quote:

b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course.)

In levels of increasing incorrectness:
1> it can't be done.
2> use markers for "unused value".
3> Implement a hash table instead of an array. Takes practical constant time, theoretical (when you pay attention to the dots on the i's) lg n time.
4> Implement a skip list instead of an array. Takes probabalistic-average lg n time.

Dragonlich · 02-21-2009, 01:08 AM

Quote:

Originally Posted by cheerios

Describe how one can implement each of the following operations on an array so that the time it takes does not depend on the array's size n.
a. Delete the ith element of an array(1<=i<=n).
b. Delete the ith element of a sorted array (the remaining array has to stay sorted, of course.)

If you could solve both problems independently:
a) just set array[i ] to zero/null.
b) use linked lists (pointers). simply drop item i, have item [i-1] point to item [i+1].

To solve both problems at once seems impossible. With a normal array, problem b seems impossible, because sorting an array takes n steps at least. With linked lists, problem a seems impossible, because deleting item i is dependent on the size of n (you have to search for the item).

I got the big olde book of data structures, which tells me that no matter which data structure you use, either a or b depends on the array size n in some way. The most efficient option I saw was a heap (https://users.cs.jmu.edu/bernstdh/we...troduction.php).

ratbastid · 02-21-2009, 08:05 AM

Really? 5-year-old programming homework solutions?

n0nsensical · 02-21-2009, 05:09 PM

Okay I just rewrote the answer to part (a) then realized that was exactly what Yakk already said... Heh. The null thing is even worse because then you need to rewrite all your code to check for nulls whenever you iterate or dereference an array (and you WILL forget that little nested for loop that causes your program to randomly crash and burn), and you can't have a valid value equal to null in the array.

For the sorted array it's a little trickier because you need to move things around so it's still dependent on the size of the array. I don't believe it's technically possible to do that for any given sorted array without resorting to even worse hackery which kind of defeats the whole purpose of using one. If you really need to do deletions in O(1) time maybe you are using the wrong data structure.

I would be really curious to find out the instructor's 'answer' to part (b), but I don't imagine cheerios will be back to tell us.

A hash table supports deletion in O(1) time, but by most definitions a hash table is not an array. There are exceptions such as in PHP where an 'array' is actually implemented as a hash table, but a PHP array is quite different from a traditional low-level array.

Martian · 02-21-2009, 06:29 PM

Quote:

Originally Posted by ratbastid

Really? 5-year-old programming homework solutions?

Apparently. For a banned member, no less.

ratbastid · 02-21-2009, 09:26 PM

Quote:

Originally Posted by n0nsensical

that was exactly what Yakk already said...

...five YEARS ago!!!

I have to admit. I miss cheerios a lot.

n0nsensical · 02-21-2009, 09:31 PM

Quote:

Originally Posted by ratbastid

...five YEARS ago!!!

I have to admit. I miss cheerios a lot.

I remember when she got banned, I couldn't figure it out, hell I still don't know.

01-22-2004, 07:28 PM	#2 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	You mean a regular array, as in the C++ declaration Code: int x[100]; ? You don't normally delete elements from an array. I don't know of any data structure that supports deletion in O(1) time. I mean a hash table can do that if the set of keys is the same size as the potential set of elements. But that isn't much different then deleting from a regular array. __________________ "It better be funny" Last edited by kel; 01-22-2004 at 07:34 PM..

01-22-2004, 08:39 PM	#4 (permalink)
sailor beauty in the breakdown Location: Chapel Hill, NC	Ha, there was a CS major explaining this to someone in the library this afternoon. I didnt join in because I dont know much about programming, but IIRC, she said just what you did--you cant really delete them, you have to make a new array minus the element you wish to delete, or, if you can, just set the element equal to null. __________________ "Good people do not need laws to tell them to act responsibly, while bad people will find a way around the laws." --Plato

01-22-2004, 08:56 PM	#5 (permalink)
kel WARNING: FLAMMABLE Location: Ask Acetylene	Creating a new array and copying is an O(n) operation so that can't be it. Arrays don't have null values, unless they are arrays of pointers, which isn't specified. Question = nonsensical. __________________ "It better be funny"

01-23-2004, 09:08 AM	#7 (permalink)
The_Dude The GrandDaddy of them all! Location: Austin, TX	i'm thinking hash tables here. the actual table being a linked list which keeps track of the previous and the next elements. if the hash table is organized by element #, then u should be able to go into x element and remove it. same thing with the b part. __________________ "Luck is what happens when preparation meets opportunity." - Darrel K Royal

02-21-2009, 05:09 PM	#12 (permalink)
n0nsensical Junkie Location: San Francisco	Okay I just rewrote the answer to part (a) then realized that was exactly what Yakk already said... Heh. The null thing is even worse because then you need to rewrite all your code to check for nulls whenever you iterate or dereference an array (and you WILL forget that little nested for loop that causes your program to randomly crash and burn), and you can't have a valid value equal to null in the array. For the sorted array it's a little trickier because you need to move things around so it's still dependent on the size of the array. I don't believe it's technically possible to do that for any given sorted array without resorting to even worse hackery which kind of defeats the whole purpose of using one. If you really need to do deletions in O(1) time maybe you are using the wrong data structure. I would be really curious to find out the instructor's 'answer' to part (b), but I don't imagine cheerios will be back to tell us. A hash table supports deletion in O(1) time, but by most definitions a hash table is not an array. There are exceptions such as in PHP where an 'array' is actually implemented as a hash table, but a PHP array is quite different from a traditional low-level array. __________________ "Prohibition will work great injury to the cause of temperance. It is a species of intemperance within itself, for it goes beyond the bounds of reason in that it attempts to control a man's appetite by legislation, and makes a crime out of things that are not crimes. A Prohibition law strikes a blow at the very principles upon which our government was founded." --Abraham Lincoln Last edited by n0nsensical; 02-21-2009 at 06:31 PM.. Reason: i am all fucked up!

01-22-2004, 07:41 PM	#3 (permalink)
cheerios Banned Location: 'bout 2 feet from my iMac	yeah, i mean a regular array. that's why this has me baffled. 'cuz you don't delete out of an array 'cuz it's a waste of time!

01-23-2004, 07:06 AM	#6 (permalink)
hlprmnky Upright Location: MN, USA	Well, I agree that the question doesn't seem to make a lot of sense. The closest thing I can come to that's a "real" answer (i.e., not just 'set the array element to null') is this: for(j = i; j < array.length - 1; j++) { array[j] = array[j + 1]; } array[array.length] = null; Although in a worst-case analysis this is in fact O(n), it doesn't depend directly on the length of the array in the same way that copying all the elements does. Be sure to let us know what the answer is!

01-23-2004, 01:12 PM	#8 (permalink)
cheerios Banned Location: 'bout 2 feet from my iMac	well, I went in to ask, but our department is going through acredditation this semester and the entire dept is out for meetings the whole day. I am NOT amused. So, your (and my) answer will have to wait until monday.

02-21-2009, 08:05 AM	#11 (permalink)
ratbastid Darth Papa Location: Yonder	Really? 5-year-old programming homework solutions?