\nToday’s Little Program is an exercise that solves the following problem:\n<\/p>\n
\n\nGiven a JavaScript array
a<\/code>\nand an unsorted arrayindices<\/code>\n(possibly containing duplicates),\ncalculate the result of deleting all of the elements from the original\narray as specified by the indices.\nFor example, suppose\na = [\"alice\", \"bob\", \"charles\", \"david\", \"eve\"]<\/code>\nand\nindices = [2, 4, 2, 0]<\/code>.\n<\/p>\n\n<\/tr>\n
\n a[0] <\/td>\n= \"alice\";<\/td>\n<\/tr>\n\n a[1] <\/td>\n= \"bob\";<\/td>\n<\/tr>\n\n a[2] <\/td>\n= \"charles\";<\/td>\n<\/tr>\n\n a[3] <\/td>\n= \"david\";<\/td>\n<\/tr>\n\n a[4] <\/td>\n= \"eve\";<\/td>\n<\/tr>\n\n a.length<\/td>\n= 5;<\/td>\n<\/tr>\n<\/table>\n\nThe indices specify that elements 2 (charles), 4 (eve),\n2 (charles again, redundant), and 0 (alice) should be\ndeleted from the array,\nleaving bob and david.\n<\/p>\n<\/blockquote>\n
\nNow, if you had to delete only one element from the array,\nit is pretty simple:\n<\/p>\n
\na.splice(n, 1);\n<\/pre>\n\nThe trick with removing multiple elements is\nthat deleting one element shifts the indices,\nwhich can throw off future calculations.\nOne solution is to remove the highest-indexed element first;\nin other words, operate on the indices in reverse sorted order.\n<\/p>\n
\nindices.sort().reverse().forEach(function(n) { a.splice(n, 1); });\n<\/pre>\n\nThis technique does still suffer from the problem that if\nthere are duplicates in the indices,\nextraneous elements get deleted by mistake.\n<\/p>\n
\nAnother approach is to reinterpret the problem by focusing not on\nthe deletion but on the survivors:\nProduce the array consisting of elements whose indices are not\nin the list of indices to be deleted.\n<\/p>\n
\na = a.filter(function(e, i) { return indices.indexOf(i) >= 0; });\n<\/pre>\n\nThe above approach works well if the list of indices to be deleted\nis short, but it gets quite expensive if the list is long.\n<\/p>\n
\nMy approach is to use the fact that JavaScript arrays can be sparse.\nThis is a side effect of the fact that JavaScript array indices\nare actually object properties;\nthe only thing that makes arrays different from generic objects in\na language-theoretic sense is\nthe magic
length<\/code> property:\n<\/p>\n\n
- If a new property is added, and the property name\n is the stringification of a whole number,\n then the
length<\/code> is updated to the numeric\n value of the added property name, plus 1.<\/p>\n- If the
length<\/code> property is modified programmatically,\n the new value must be a whole number,\n and\n all properties which are the stringification of a whole number\n greater than or equal to the newlength<\/code>\n are deleted.\n<\/ul>\n\n(See\n\nECMA-262<\/a>\nsections\n\n15.4<\/a>,\n\n15.4.5.1<\/a>,\nand\n\n15.4.5.2<\/a>\nfor nitpicky details.)\n<\/p>\n
\nThe first step, then, is to delete all the indices that need to be deleted.\n<\/p>\n
\nindices.forEach(function(n) { delete a[n]; });\n<\/pre>\n\nWhen applied to our sample data, this leaves\n<\/p>\n
\n<\/tr>\n
\n a[1] <\/td>\n= \"bob\";<\/td>\n<\/tr>\n\n a[3] <\/td>\n= \"david\";<\/td>\n<\/tr>\n\n a.length<\/td>\n= 5;<\/td>\n<\/tr>\n<\/table>\n\nwhich\ngets printed in a rather goofy way:\n
a = [, \"bob\", , \"dave\", ]<\/code>.\n<\/p>\n\nThe next step is to close up the gaps.\nWe take advantage of the fact that the
Array<\/code>\nenumeration methods operate on indices 0 throughlength - 1<\/code>\nand that they skip missing elements<\/i>.\nTherefore, I can simply apply a dummy filter:\n<\/p>\n\na = a.filter(function() { return true; });\n<\/pre>\n\nExercise<\/b>:\nWhat is the difference (aside from performance) between\n
a.push(1);<\/code> anda = a.concat(1);<\/code>?\nHow is this question relevant to today's exercise?<\/p>\n","protected":false},"excerpt":{"rendered":"Today’s Little Program is an exercise that solves the following problem: Given a JavaScript array a and an unsorted array indices (possibly containing duplicates), calculate the result of deleting all of the elements from the original array as specified by the indices. For example, suppose a = [“alice”, “bob”, “charles”, “david”, “eve”] and indices = […]<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-223","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"
Today’s Little Program is an exercise that solves the following problem: Given a JavaScript array a and an unsorted array indices (possibly containing duplicates), calculate the result of deleting all of the elements from the original array as specified by the indices. For example, suppose a = [“alice”, “bob”, “charles”, “david”, “eve”] and indices = […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/223","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=223"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/223\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=223"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=223"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=223"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}