Re: Is it possible to delete an element from a sorted array with O(1) time?

Oh my. I think this all issued from the two of us using different readings
of a two letter word.


Alf P. Steinbach wrote:

* Kai-Uwe Bux:
Alf P. Steinbach wrote:

* Kai-Uwe Bux:
Alf P. Steinbach wrote:

* Kai-Uwe Bux:
Anyway, your interpretation (whether reasonable or not) of "deletion"
was not waranted by my post at this point. It was clear from parts(*)
that you snipped that delete was supposed to have the effect of
reindexing the elements after the deletion (purely a matter of
interface not of implementation and without any obvious implications
on the complexity).
Deleting an element in a cursor gap array does "reindex" the following
elements -- in constant time. :-)
Unrelated to the question at hand since delete was also (and you know
and knew that) supposed to be at random positions. Unfortunately, those
constraints are now invisible do to your snipping.


Please, no more "argument ad ignorantium".
That does not even exist (neither in latin nor in english).

Should you mean "argumentum ad ignorantiam" (latin) or "argument from
ignorance" (english), I will note that I did not commit that fallacy.
I'm sure that you can easily read up on the structure we have
discussed, if nowhere else, then in Wikipedia.
The cursor gap structure does not provide the answer to the question I
posed, which (as you may or may not have noticed) was different from
the question of the OP. Unfortunately, both are gone due to your
snipping.

Anyway, by now it has become clear that you answered neither correctly.
Kai Uwe, you anger me by being so dishonest.

Well, I was angry too, when I wrote this. I guess that makes us even :-)

OK, let's forgive and -- well, not forget, because by forgetting one
does not learn anything. I was really pi**ed off because I couldn't
believe you believed anything of what you wrote. 'Nuff said.


I apologize for hurting your feelings, although I do not see that I am
being dishonest.

For reference: The OPs question was:

Is it possible to delete an element from a sorted array with O(1) time?

And your answer was:

> Hi, folks,
> Is it possible to delete an element from a sorted array with O(1)
> time?

Yes.

(no further qualifications or comments)

Yes. A simple demonstration: remove the last element of a sorted
std::vector<int> v by v.resize( v.size() - 1 ). This performs "delete
an element from a sorted array with O(1) time", exactly as specified in
the question.

That demonstrates that there is _some element_ that you can remove in
constant time. I find it more natural to interpret the "an element" in the
question as "any element" whereas you interpret it as "some element". For
instance, I would not read the question "can you sort a finite sequence of
integers in constant time" as asking whether there are sequences that can
be sorted in constant time.

Furhermore, under all reasonable direct interpretations of the question,
without adding in extra requirements the answer is yes.

Already reading "an" as "any" as opposed to "some" makes it very unlikely
that all reasonable direct interpretations of the question yield the
answer "yes". There is an ambiguity in the English language and
interpretations are used to resolve those ambiguities. It appears that our
linguistic intuitions differ as to which initial resolution of the
ambiguity is more natural.


Only by adding extra requirements is it possible to end up with less
than unconditional yes. And the answer is then not unqualified "no" but
"it is possible to add requirements such that deletion of an arbitrary
element is not possible in constant time". Which is meaningless because
adding requirements so that something becomes impossible can nearly
always be done, not matter the task.

It is only meaningless if those constraints remain unspecified. With
specific constraint, it just makes the question more precise (thereby, of
course, changing the question).


I was trying hard to make question of the OP more precise by making
requirements explicit. Eventually, I came up with the _question_ whether
there is a data structure that one could use to implement std::vector<>
(without contiguity of memory) or std::deque<> so that erase() at least
for a single element becomes constant time while keeping the complexity
of at() constant time, too. In fact, I would contend that this is the
most natural reading of the OPs question in a general programming context
where "array" does not necessarily refer to a raw array but could refer
to a higher level sequence container. And I also conjecture that the
answer to this question is "no" (although I am not sure about this).

In the general case I think the answer to that amended question is "no",
but it's easy to add further constraints so that the answer turns once
more, back to "yes". For example, the constraint that deletions are
only at the end, or, for another example, that all elements are the same
value, or, for a third example, that there are no more than K delete
operations, where K is any not unreasonably large constant (in this case
reindexing can be computed in constant time based on the deletion
operation history). In short, almost any answer can be forced for any
question by adding constraints, requirements and reinterpretations as
one pleases, but the question is then no longer the original one.

True.


You seemed to try hard to keep the answer "yes" by coming up with red
herrings (like the cursor gap, which ceased to be a possible
implementation once some requirements had been made explicit)

A cursor gap array is a reasonable model for the OP's question. It is
an array by any reasonable definition of array, with random access read
and write operations. And it supports constant time deletion at the
cursor position -- the OP didn't specify random access deletion.

Actually, that is exactly the issue of whether "an" is better read as "any"
or "some". I do think that random access deletion is what the OP was asking
about. That reading is just more natural to me (essentially because I think
if the OP was asking about particular elements like the beginning or the
end or the element under the cursor, he would have said some more).


Any impossibility is solely due to explicitly excluding it as possible,
and such exclusion was neither specified nor implied by the OP.

Whether the OP is happy learning that _some_ elements in an array can be
deleted in constant time is for the OP to decide. An unqualified "yes"
based upon the assumption that this is all that was asked for is a little
stretched in my opinion. Anyway, by now all those additional assumptions
that allow constant time deletion have been made clear so that the OP will
have a pretty good idea what can be achieved and what cannot.


or creative readings of the
problem (like having erase introduce invalid indices, which was a good
catch initially as it forced making even more requirements explicit).

It's not a creative reading. It is an often used technique for solving
the problem the OP literally asked about. One catch is that deletion
operations need to be sparse lest one ends up with mostly "blank space".


All
these exercises are educationally useful; but the point of those
exercises should be to make the question clearer not to keep the initial
answer. It is understood that as the question changes, the answer may
change, too.

Yes, but note that this means you have no basis for your statement that
I didn't answer the original correctly: I answered that correctly.

You answered it correctly given one (in my eyes not very natural)
interpretation. The answer is incorrect given a different (in my eyes much
more natural) interpretation. That is and was my basis for the claim.


Nor have you any basis for your statement (in the same sentence) that I
didn't answer your amended question correctly -- I didn't answer that
amended question at all, until now, so I absolutely did not answer it
incorrectly.

And for the same reason of not answering at all, you had not answered it
correctly, or did you? :-)

I have to admit that I chose this particularly malicious wording because I
was very annoyed by you evading the question.


Those two statements, in the same sentence, were part of what you wrote
in that posting that I could not believe you actually believed.

Well, I do believe that your answer to the OP is incorrect (because I find
your chosen interpretation less natural than mine).

And I do believe that you did not answer my question at all (as you said
yourself).

I intentionally chose an evil (although technically correct) wording to put
those two believes in one sentence out of anger. Sorry.

To make things absolutely clear, you are right: I do not and did not believe
that you answered my question incorrectly.


I will concede that the question of the OP was ambiguous (although I
think there is an obvious guess for what the meaning was supposed to be).
I will also concede that your initial answer was very useful in
triggering a discussion about the hidden assumptions underlying the
question. However, at some point you ceased to be cooperative by
intentionally misreading requirements that had been made clear already
(and throwing around bogus accusations of fallacious reasoning, which
annoyed me most). At least, that is how I see it.

As I see it the technical issues are clearcut, and the earlier
fallacious reasoning very clearly exposed. For a technical example, the
idea that a cursor gap array does not qualify as an array, is
fallacious, based on mistaken ideas about random access.

I will get to that below.

For another
example, regarding the general rhetoric, the idea that not answering an
irrelevant question is equivalent to answering it incorrectly, is
fallacious.

See above: I did not claim that you answered the question incorrectly.

As for whether my question is irrelevant, I will note that this depends on
which interpretation of the OPs question has a better claim to naturality.
Naturally, I think that would be mine :-)


But hey, everybody, including me, do fallacious reasoning now and then.


The upshot is: I think the answer to the OPs question _in its most
natural interpretation_ is "no", although I have no proof that there is
no implementation that would cut it.

We evidently differ greatly in what can be considered a natural
interpretation. To me imposing arbitrary /limiting/ requirements and
replacing general terms with particular concrete instances, and
considering only one particular such transformation, is not a natural
way to interpret a question.

I see now that we already departed on the meaning of "an element". From your
point of view, what I did must have looked like introducing arbitrary
requirements. From my point of view, I was merely making implicit
assumptions explicit. E.g., I interpreted deletion to mean random access
deletion, and I interpreted "array" as meaning a data structure that has
constant time (or at least better than linear) random read/write access and
(after you pointed that out) does not have gaps in the indexing sequence
(std::vector or std::deque being the prime examples).

BTW: cursor-gap structures, you are right, are examples of arrays in this
sense. What happened at that point is that I misunderstood you big time:
when you said they do not support random access, you were refering to
random access deletion; and I understood you were refering to random access
read/write. The reason for my misunderstanding is that up to that point it
simply had not occurred to me that OPs question could be understood other
than meaning whether _any_ element (random index) could be deleted in
constant time. So, when I read your paragraph

Of course, the most natural way (what cursor gap is all about) doesn't
support random access, but then, that wasn't asked for even with the
off-topic general programming interpretation of the OP's question.

I thought "what is he talking about? cursor-gaps as I know them do support
random access" (namely for read and write).

I now see that I should have taken into account the next paragraph:

For random access deletions you can implement ...

which, indeed, makes it clear that you were talking about random access
deletions not being supported by cursor-gaps.

Indeed, my bad.


When I ask whether it's possible to fly
from Oslo to Trondheim on a given day, I don't want the travel agent to
impose some extra to him "most natural" requirements such that the
flight must be via Berlin, London and New York, and report "sorry, no
such flight is available".

When someone ask me "can you fix a broken bicycle?" I would not answer with
an unqualified "yes" simply because there are some broken bicycles I know
how to fix. The OPs question is ambiguous in precisely that sense; and I
think that the resolution

an --> any

is more suitable an interpretation for that question than the resolution

an --> some

BTW:red floyd posted in comp.lang.c++:

Daniel Kraft wrote:
Hi, folks,
Is it possible to delete an element from a sorted array with O(1)
time?

Yes.

How that?

Deleting from any array (sorted or not) takes O(n) except when deleting
from the end or the beginning. (I assume you actually mean an "array"
and not some special sort of container like linked list).


[NITPICKY-SMARTALECKY]
OP didn't specify *any* element, he specified *an* element. So yes, in
any array, there exists an element which can be deleted from a sorted
array in O(1) time (namely the last one).
[/NITPICKY-SMARTALECKY]

Until your last post, I did not expect that your initial answer was actually
based upon the very same reading of the OPs question.


However, I am glad that now all technical issues have been resolved.

As to which interpretation is more natural, I am willing to agree to
disagree. In the end, should the OP have followed the discussion, he will
find more technical information in this thread than he can claim he asked
for :-)


Let me again apologize for my angry post. I felt very annoyed since you kept
evading an issue that I felt was at the core of the OPs question. Now I see
that you (due to a very different interpretation) must have felt that I was
going off a tangent that is irrelevant since unrelated to the OPs question.
Sorry.


Best

Kai-Uwe Bux
.

Relevant Pages

  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... Is it possible to delete an element from a sorted array with Otime? ... And the answer is then not unqualified "no" but "it is possible to add requirements such that deletion of an arbitrary element is not possible in constant time". ... As I see it the technical issues are clearcut, and the earlier fallacious reasoning very clearly exposed. ...
    (comp.programming)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... misconception that general array insertion and deletion is ... I read about cursor gap structures when I ... constant time random access by index and constant time entry removal ...
    (comp.programming)
  • Re: Is it possible to delete an element from a sorted array with O(1) time?
    ... misconception that general array insertion and deletion is necessarily ... you might want to look up cursor gap structures somewhere. ... focused on its support for random access to its elements. ...
    (comp.programming)
  • Re: Developing BBC BASIC
    ... interpretation should be used in any cases of ambiguity, ... None of my extensions should result in surprises, ... can *always* re-DIM an existing array so ...
    (comp.sys.acorn.programmer)
  • RE: assembler question (strong typing)
    ... All that IO did was change the interpretation of the index expression. ... For any subscripted access to an array, ... APL is a language where typing was implicit, but could be changed on the ... scope or local scope (within a ...
    (bit.listserv.ibm-main)