how is the time complexity of dict.clear() is O(1) in python?
According to https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt, time complexity of dict.clear() is O(1).
As far as I know, dict.clear() is not same as assigning dict = {}, as dict.clear() make changes to same dict, while dict = {} create a new dict.
Now if dict.clear() is clearing the same dict object, then how it can complete it in O(1).
python dictionary time-complexity python-internals
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
add a comment |
According to https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt, time complexity of dict.clear() is O(1).
As far as I know, dict.clear() is not same as assigning dict = {}, as dict.clear() make changes to same dict, while dict = {} create a new dict.
Now if dict.clear() is clearing the same dict object, then how it can complete it in O(1).
python dictionary time-complexity python-internals
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
2
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
5
The implemention forPyDict_Clearcan be found here.
– timgeb
Nov 22 at 20:47
4
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]);that doesn't look likeO(1)to me... seems that I was wrong
– Jean-François Fabre
Nov 22 at 20:49
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50
add a comment |
According to https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt, time complexity of dict.clear() is O(1).
As far as I know, dict.clear() is not same as assigning dict = {}, as dict.clear() make changes to same dict, while dict = {} create a new dict.
Now if dict.clear() is clearing the same dict object, then how it can complete it in O(1).
python dictionary time-complexity python-internals
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
According to https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt, time complexity of dict.clear() is O(1).
As far as I know, dict.clear() is not same as assigning dict = {}, as dict.clear() make changes to same dict, while dict = {} create a new dict.
Now if dict.clear() is clearing the same dict object, then how it can complete it in O(1).
python dictionary time-complexity python-internals
python dictionary time-complexity python-internals
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
edited Nov 22 at 20:49
hiro protagonist
18.1k63860
18.1k63860
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
asked Nov 22 at 20:44
Harsh Sharma
7,72721019
7,72721019
2
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
5
The implemention forPyDict_Clearcan be found here.
– timgeb
Nov 22 at 20:47
4
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]);that doesn't look likeO(1)to me... seems that I was wrong
– Jean-François Fabre
Nov 22 at 20:49
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50
add a comment |
2
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
5
The implemention forPyDict_Clearcan be found here.
– timgeb
Nov 22 at 20:47
4
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]);that doesn't look likeO(1)to me... seems that I was wrong
– Jean-François Fabre
Nov 22 at 20:49
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50
2
2
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
5
5
The implemention for
PyDict_Clear can be found here.– timgeb
Nov 22 at 20:47
The implemention for
PyDict_Clear can be found here.– timgeb
Nov 22 at 20:47
4
4
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]); that doesn't look like O(1) to me... seems that I was wrong– Jean-François Fabre
Nov 22 at 20:49
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]); that doesn't look like O(1) to me... seems that I was wrong– Jean-François Fabre
Nov 22 at 20:49
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50
add a comment |
2 Answers
2
active
oldest
votes
Some rationale for why it is being claimed to be O(1):
The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.
answered Nov 22 at 21:20
arshajii
101k18180250
add a comment |
I first thought that dict.clear just performed some reference decrease to let the garbage collector do the dirty non-O(1) work, but looking at the source code (thanks timgeb for providing the link) it doesn't seem to be that:
oldvalues = mp->ma_values;
if (oldvalues == empty_values)
return;
/* Empty the dict... */
dictkeys_incref(Py_EMPTY_KEYS);
mp->ma_keys = Py_EMPTY_KEYS;
mp->ma_values = empty_values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
/* ...then clear the keys and values */
if (oldvalues != NULL) {
n = oldkeys->dk_nentries;
for (i = 0; i < n; i++)
Py_CLEAR(oldvalues[i]);
What I see is that if the dictionary had values, then a loop is performed to decrease references those values and set the pointers to NULL. So seems to be O(n) not O(1) since it depends on the number of the values.
When you assign to a new dict like this d = {}, this is O(1), but the garbage collector must delete the old object when not referenced anymore. That may not be right when assigning, but that will happen, unless python quits abruptly.
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
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%2f53437779%2fhow-is-the-time-complexity-of-dict-clear-is-o1-in-python%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
Some rationale for why it is being claimed to be O(1):
The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.
answered Nov 22 at 21:20
arshajii
101k18180250
add a comment |
Some rationale for why it is being claimed to be O(1):
The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.
answered Nov 22 at 21:20
arshajii
101k18180250
add a comment |
Some rationale for why it is being claimed to be O(1):
The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.
answered Nov 22 at 21:20
arshajii
101k18180250
Some rationale for why it is being claimed to be O(1):
The clear() method is actually just assigning the internal dictionary structures to new empty values (as can be seen in the source). The seemingly O(n) part is a result of decrementing reference counts, and other GC-related stuff. But this is purely a function of the GC approach that CPython uses (i.e. reference counting); you can envision different approaches that wouldn't require explicit cleanup like this, or where the cleanup would happen much later (or even be amortized away). Since ideally the time complexity of clear() shouldn't depend on the underlying GC approach, all GC-related parts are omitted, making it "O(1)". IMO this is mostly a definitional argument than anything else, but this is at least some justification.
answered Nov 22 at 21:20
arshajii
101k18180250
answered Nov 22 at 21:20
arshajii
101k18180250
answered Nov 22 at 21:20
arshajii
101k18180250
answered Nov 22 at 21:20
arshajii
101k18180250
101k18180250
add a comment |
add a comment |
I first thought that dict.clear just performed some reference decrease to let the garbage collector do the dirty non-O(1) work, but looking at the source code (thanks timgeb for providing the link) it doesn't seem to be that:
oldvalues = mp->ma_values;
if (oldvalues == empty_values)
return;
/* Empty the dict... */
dictkeys_incref(Py_EMPTY_KEYS);
mp->ma_keys = Py_EMPTY_KEYS;
mp->ma_values = empty_values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
/* ...then clear the keys and values */
if (oldvalues != NULL) {
n = oldkeys->dk_nentries;
for (i = 0; i < n; i++)
Py_CLEAR(oldvalues[i]);
What I see is that if the dictionary had values, then a loop is performed to decrease references those values and set the pointers to NULL. So seems to be O(n) not O(1) since it depends on the number of the values.
When you assign to a new dict like this d = {}, this is O(1), but the garbage collector must delete the old object when not referenced anymore. That may not be right when assigning, but that will happen, unless python quits abruptly.
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
add a comment |
I first thought that dict.clear just performed some reference decrease to let the garbage collector do the dirty non-O(1) work, but looking at the source code (thanks timgeb for providing the link) it doesn't seem to be that:
oldvalues = mp->ma_values;
if (oldvalues == empty_values)
return;
/* Empty the dict... */
dictkeys_incref(Py_EMPTY_KEYS);
mp->ma_keys = Py_EMPTY_KEYS;
mp->ma_values = empty_values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
/* ...then clear the keys and values */
if (oldvalues != NULL) {
n = oldkeys->dk_nentries;
for (i = 0; i < n; i++)
Py_CLEAR(oldvalues[i]);
What I see is that if the dictionary had values, then a loop is performed to decrease references those values and set the pointers to NULL. So seems to be O(n) not O(1) since it depends on the number of the values.
When you assign to a new dict like this d = {}, this is O(1), but the garbage collector must delete the old object when not referenced anymore. That may not be right when assigning, but that will happen, unless python quits abruptly.
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
add a comment |
I first thought that dict.clear just performed some reference decrease to let the garbage collector do the dirty non-O(1) work, but looking at the source code (thanks timgeb for providing the link) it doesn't seem to be that:
oldvalues = mp->ma_values;
if (oldvalues == empty_values)
return;
/* Empty the dict... */
dictkeys_incref(Py_EMPTY_KEYS);
mp->ma_keys = Py_EMPTY_KEYS;
mp->ma_values = empty_values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
/* ...then clear the keys and values */
if (oldvalues != NULL) {
n = oldkeys->dk_nentries;
for (i = 0; i < n; i++)
Py_CLEAR(oldvalues[i]);
What I see is that if the dictionary had values, then a loop is performed to decrease references those values and set the pointers to NULL. So seems to be O(n) not O(1) since it depends on the number of the values.
When you assign to a new dict like this d = {}, this is O(1), but the garbage collector must delete the old object when not referenced anymore. That may not be right when assigning, but that will happen, unless python quits abruptly.
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
I first thought that dict.clear just performed some reference decrease to let the garbage collector do the dirty non-O(1) work, but looking at the source code (thanks timgeb for providing the link) it doesn't seem to be that:
oldvalues = mp->ma_values;
if (oldvalues == empty_values)
return;
/* Empty the dict... */
dictkeys_incref(Py_EMPTY_KEYS);
mp->ma_keys = Py_EMPTY_KEYS;
mp->ma_values = empty_values;
mp->ma_used = 0;
mp->ma_version_tag = DICT_NEXT_VERSION();
/* ...then clear the keys and values */
if (oldvalues != NULL) {
n = oldkeys->dk_nentries;
for (i = 0; i < n; i++)
Py_CLEAR(oldvalues[i]);
What I see is that if the dictionary had values, then a loop is performed to decrease references those values and set the pointers to NULL. So seems to be O(n) not O(1) since it depends on the number of the values.
When you assign to a new dict like this d = {}, this is O(1), but the garbage collector must delete the old object when not referenced anymore. That may not be right when assigning, but that will happen, unless python quits abruptly.
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
edited Nov 22 at 21:05
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
answered Nov 22 at 20:56
Jean-François Fabre
100k954109
100k954109
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%2f53437779%2fhow-is-the-time-complexity-of-dict-clear-is-o1-in-python%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
2
maybe by trashing the internal data structure and leave garbage collector do the dirty non O(1) work. It's NOT looping through elements and delete one by one.
– Jean-François Fabre
Nov 22 at 20:46
5
The implemention for
PyDict_Clearcan be found here.– timgeb
Nov 22 at 20:47
4
for (i = 0; i < n; i++) Py_CLEAR(oldvalues[i]);that doesn't look likeO(1)to me... seems that I was wrong– Jean-François Fabre
Nov 22 at 20:49
interestingly, complexity of clear isn't discussed here wiki.python.org/moin/TimeComplexity
– Jean-François Fabre
Nov 22 at 20:50