Is there a PYTHON data structure with O(log n) deletion/insertion and supports indexing?
Multi tool use
While doing competitive coding, I came across a scenario where I needed O(log n) removal, while being able to support indexing (O(1) preferably) for a binary search. I essentially need to locate an element using a binary approach (currently using bisect), and then remove that element I found, which is currently a O(n) operation. I obviously cannot use libraries that are not built in, hence why blist is not an option, and I can't use a set because that doesn't support indexing. Is there an alternative, or is using something like a binary tree the only option. If so, are there any easy pre-defined libraries in python that I am able to use?
python
asked Dec 28 '18 at 3:29
Justin Choi
102
add a comment |
While doing competitive coding, I came across a scenario where I needed O(log n) removal, while being able to support indexing (O(1) preferably) for a binary search. I essentially need to locate an element using a binary approach (currently using bisect), and then remove that element I found, which is currently a O(n) operation. I obviously cannot use libraries that are not built in, hence why blist is not an option, and I can't use a set because that doesn't support indexing. Is there an alternative, or is using something like a binary tree the only option. If so, are there any easy pre-defined libraries in python that I am able to use?
python
asked Dec 28 '18 at 3:29
Justin Choi
102
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07
add a comment |
While doing competitive coding, I came across a scenario where I needed O(log n) removal, while being able to support indexing (O(1) preferably) for a binary search. I essentially need to locate an element using a binary approach (currently using bisect), and then remove that element I found, which is currently a O(n) operation. I obviously cannot use libraries that are not built in, hence why blist is not an option, and I can't use a set because that doesn't support indexing. Is there an alternative, or is using something like a binary tree the only option. If so, are there any easy pre-defined libraries in python that I am able to use?
python
asked Dec 28 '18 at 3:29
Justin Choi
102
While doing competitive coding, I came across a scenario where I needed O(log n) removal, while being able to support indexing (O(1) preferably) for a binary search. I essentially need to locate an element using a binary approach (currently using bisect), and then remove that element I found, which is currently a O(n) operation. I obviously cannot use libraries that are not built in, hence why blist is not an option, and I can't use a set because that doesn't support indexing. Is there an alternative, or is using something like a binary tree the only option. If so, are there any easy pre-defined libraries in python that I am able to use?
python
python
asked Dec 28 '18 at 3:29
Justin Choi
102
asked Dec 28 '18 at 3:29
Justin Choi
102
asked Dec 28 '18 at 3:29
Justin Choi
102
asked Dec 28 '18 at 3:29
Justin Choi
102
asked Dec 28 '18 at 3:29
Justin Choi
102
102
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07
add a comment |
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07
add a comment |
1 Answer
1
active
oldest
votes
Python does not appear to have such a structure in the standard library.
I'm not exactly sure of your needs, but since you considered using a set, that means you don't need duplicate items. Consider not changing the length of the list for a delete. Instead, replace the element you want to remove with its next-highest (non-equal) neighbor to the right. (If it happens to be the last element, you can just pop it.) The length and general indexing will be wrong, but a binary search will still work, which might be all that you need the indexing for.
Say you have [0,1,2,3,4,5] and you want to remove the 3. Make the list [0,1,2,4,4,5]. If you then want to remove the 4, make it [0,1,2,5,5,5].
You can use a binary search to find both ends of the run, which gives you the O(log n) removal you want. Use bisect_left first, and then pass in the answer from that to restrict the part of the list searched by bisect_right. Once you know the bounds, Python can assign the whole slice at once.
If you then want to remove the 5, pop them off [0,1,2]. Removal at the end of the list is more efficient since it won't require allocating a new array.
You can clean up the duplicates occasionally for better amortized performance, or if you need the length or something. Maybe when the number of "deletions" reaches a certain fraction of the original length. Don't go through a set, because you'd have to sort again. (OrderedDict.fromkeys could work, but you'd still have to build a list from the .keys()). Just copy the list while skipping over the duplicates, like
itr = iter(old)
new = [next(itr)]
for e in itr:
if e is not new[-1]:
new.append(e)
answered Dec 28 '18 at 7:08
gilch
3,501614
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53953359%2fis-there-a-python-data-structure-with-olog-n-deletion-insertion-and-supports-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Python does not appear to have such a structure in the standard library.
I'm not exactly sure of your needs, but since you considered using a set, that means you don't need duplicate items. Consider not changing the length of the list for a delete. Instead, replace the element you want to remove with its next-highest (non-equal) neighbor to the right. (If it happens to be the last element, you can just pop it.) The length and general indexing will be wrong, but a binary search will still work, which might be all that you need the indexing for.
Say you have [0,1,2,3,4,5] and you want to remove the 3. Make the list [0,1,2,4,4,5]. If you then want to remove the 4, make it [0,1,2,5,5,5].
You can use a binary search to find both ends of the run, which gives you the O(log n) removal you want. Use bisect_left first, and then pass in the answer from that to restrict the part of the list searched by bisect_right. Once you know the bounds, Python can assign the whole slice at once.
If you then want to remove the 5, pop them off [0,1,2]. Removal at the end of the list is more efficient since it won't require allocating a new array.
You can clean up the duplicates occasionally for better amortized performance, or if you need the length or something. Maybe when the number of "deletions" reaches a certain fraction of the original length. Don't go through a set, because you'd have to sort again. (OrderedDict.fromkeys could work, but you'd still have to build a list from the .keys()). Just copy the list while skipping over the duplicates, like
itr = iter(old)
new = [next(itr)]
for e in itr:
if e is not new[-1]:
new.append(e)
answered Dec 28 '18 at 7:08
gilch
3,501614
add a comment |
Python does not appear to have such a structure in the standard library.
I'm not exactly sure of your needs, but since you considered using a set, that means you don't need duplicate items. Consider not changing the length of the list for a delete. Instead, replace the element you want to remove with its next-highest (non-equal) neighbor to the right. (If it happens to be the last element, you can just pop it.) The length and general indexing will be wrong, but a binary search will still work, which might be all that you need the indexing for.
Say you have [0,1,2,3,4,5] and you want to remove the 3. Make the list [0,1,2,4,4,5]. If you then want to remove the 4, make it [0,1,2,5,5,5].
You can use a binary search to find both ends of the run, which gives you the O(log n) removal you want. Use bisect_left first, and then pass in the answer from that to restrict the part of the list searched by bisect_right. Once you know the bounds, Python can assign the whole slice at once.
If you then want to remove the 5, pop them off [0,1,2]. Removal at the end of the list is more efficient since it won't require allocating a new array.
You can clean up the duplicates occasionally for better amortized performance, or if you need the length or something. Maybe when the number of "deletions" reaches a certain fraction of the original length. Don't go through a set, because you'd have to sort again. (OrderedDict.fromkeys could work, but you'd still have to build a list from the .keys()). Just copy the list while skipping over the duplicates, like
itr = iter(old)
new = [next(itr)]
for e in itr:
if e is not new[-1]:
new.append(e)
answered Dec 28 '18 at 7:08
gilch
3,501614
add a comment |
Python does not appear to have such a structure in the standard library.
I'm not exactly sure of your needs, but since you considered using a set, that means you don't need duplicate items. Consider not changing the length of the list for a delete. Instead, replace the element you want to remove with its next-highest (non-equal) neighbor to the right. (If it happens to be the last element, you can just pop it.) The length and general indexing will be wrong, but a binary search will still work, which might be all that you need the indexing for.
Say you have [0,1,2,3,4,5] and you want to remove the 3. Make the list [0,1,2,4,4,5]. If you then want to remove the 4, make it [0,1,2,5,5,5].
You can use a binary search to find both ends of the run, which gives you the O(log n) removal you want. Use bisect_left first, and then pass in the answer from that to restrict the part of the list searched by bisect_right. Once you know the bounds, Python can assign the whole slice at once.
If you then want to remove the 5, pop them off [0,1,2]. Removal at the end of the list is more efficient since it won't require allocating a new array.
You can clean up the duplicates occasionally for better amortized performance, or if you need the length or something. Maybe when the number of "deletions" reaches a certain fraction of the original length. Don't go through a set, because you'd have to sort again. (OrderedDict.fromkeys could work, but you'd still have to build a list from the .keys()). Just copy the list while skipping over the duplicates, like
itr = iter(old)
new = [next(itr)]
for e in itr:
if e is not new[-1]:
new.append(e)
answered Dec 28 '18 at 7:08
gilch
3,501614
Python does not appear to have such a structure in the standard library.
I'm not exactly sure of your needs, but since you considered using a set, that means you don't need duplicate items. Consider not changing the length of the list for a delete. Instead, replace the element you want to remove with its next-highest (non-equal) neighbor to the right. (If it happens to be the last element, you can just pop it.) The length and general indexing will be wrong, but a binary search will still work, which might be all that you need the indexing for.
Say you have [0,1,2,3,4,5] and you want to remove the 3. Make the list [0,1,2,4,4,5]. If you then want to remove the 4, make it [0,1,2,5,5,5].
You can use a binary search to find both ends of the run, which gives you the O(log n) removal you want. Use bisect_left first, and then pass in the answer from that to restrict the part of the list searched by bisect_right. Once you know the bounds, Python can assign the whole slice at once.
If you then want to remove the 5, pop them off [0,1,2]. Removal at the end of the list is more efficient since it won't require allocating a new array.
You can clean up the duplicates occasionally for better amortized performance, or if you need the length or something. Maybe when the number of "deletions" reaches a certain fraction of the original length. Don't go through a set, because you'd have to sort again. (OrderedDict.fromkeys could work, but you'd still have to build a list from the .keys()). Just copy the list while skipping over the duplicates, like
itr = iter(old)
new = [next(itr)]
for e in itr:
if e is not new[-1]:
new.append(e)
answered Dec 28 '18 at 7:08
gilch
3,501614
edited Dec 28 '18 at 8:11
answered Dec 28 '18 at 7:08
gilch
3,501614
answered Dec 28 '18 at 7:08
gilch
3,501614
answered Dec 28 '18 at 7:08
gilch
3,501614
3,501614
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53953359%2fis-there-a-python-data-structure-with-olog-n-deletion-insertion-and-supports-i%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
lk 7zcKW YAKbz HCOK6qDnkNDz9Frs6SJJ0jKH jnp t5ptYPH4jk,X QTOnL,9Bb4olAIT
Consider, perhaps, a treap. You will have to build it yourself, I think.
– torek
Dec 28 '18 at 3:51
Do you need indexing or binary search? Because if you just need search then any balanced search tree would do (no idea if python have some as part of standard library, but you can search yourself for red-black tree or AVL tree in python and have code ready to copy-paste)
– Alexei Levenkov
Dec 28 '18 at 4:05
A skip list or even an AA tree is probably easier to implement than a red-black tree.
– gilch
Dec 28 '18 at 6:18
You can probably get adequate performance in Python even for largish (1e7) lists with just two layers. No need for a full tree. grantjenks.com/docs/sortedcontainers/implementation.html
– gilch
Dec 28 '18 at 8:07