Lua中的table.sort:不明白这个代码？

Question

  -- original table
  t = {
    Steve = 20,
    Mary = 32,
    Tim = 15
  }

  --second table to help sort t{}    
  a = {}
  for n in pairs(t) do
    a[#a + 1] = n -- I do not completely understand this line.  
                  -- I know [#a + 1] is the iterator, but 
                  -- not a[#a + 1] and why equal that to "n"?
  end
  table.sort(a)
  for _, n in ipairs(a) do -- I do not understand the point of the underscore 
    print (n)
  end

  -- another way to perform the table.sort function        
  function pairsByKeys (t,f)
    local b = {}
    for x in pairs (t) do 
      b[#b + 1] = x
    end
    table.sort(b, f)
    local i = 0
    return function ()
      i = i + 1
      return b[i], t[b[i]]  -- I do not understand this line either?
    end
  end

我已经在我的特定代码后面的注释中提出了几个问题.我理解(大部分)为什么需要两个单独的表.一个有信息,另一个有信息ipairs.我知道之间的区别pairs和ipairs.但我不清楚a[#a + 1] = n.另外,我不明白代码for _, n in ipairs(a)......,为什么是下划线？最后,我不清楚这条线路return b[i], t[b[i]]？

你能帮我理解table.sort好一点吗？这些是PiL的直接示例.我很感激帮助!

Answer 1

首先,您应该了解Lua表的真正含义.从表面上看,它们显示为关联数组或映射(两个广为人知的CS术语),它们通常作为哈希表实现.它们以这种方式调用,因为它们将所谓的键(它是唯一的)与值相关联.它们可以被视为由键索引的键值对的集合,即以这样的方式实现,即使用(唯一)键可以非常快速地找到相应的值.

Lua表的两个主要特点,它们也使它们真正强大而灵活的数据结构(虽然起初有点难以理解),如下:

1. Lua表允许任何类型的值(除了nil)作为键.在大多数语言中,键被限制为字符串,或者是必须事先声明的特定类型.在Lua中,表格可以随时随地保存任何类型的值.因此,这样定义的表在Lua中是完全合法的:

   f = function(x) return x*x end
   t = { 1, 2, 3 }    
   tbl = {
       [t] = true,   -- `t` is the key (and a table), `true` is the value
       [f] = 12,     -- `f` is the key (and a function), `12` is the value
       [true] = f,   -- `true` is the key (boolean), `f` now is used as value
       [12] = f,     -- `12` is the key (number), `f` again as the value
       ["yup"] = t,  -- `"yup"` is the key (string), `t` now is used as value
   }
   

2. 正整数键具有特殊状态,因为它们用于模拟数组.Lua没有适当的数组概念.在Lua中,我们使用类似数组的表(也就是序列,使用新的Lua 5.2术语).很多时候,当你在Lua的上下文中看到术语数组时,实际上编写器意味着类似于数组的表,为了简单起见,我将在下面做同样的事情,不会出现歧义.Lua中的数组是什么？它是一个表,其正整数键从1某个整数开始并结束n,即其正整数键仅为数字1,2,...,n(另一种说法是说正整数键形成集合{1,2,...,n}).该数字n称为序列(数组)的长度,它是#运算符在应用于数组时返回的数字.如果表具有此属性,则将其称为序列,即可以称为数组.请注意,具有该属性的表仍然是一个数组,如果:

   • 它有额外的非数字键(例如字符串或表键);
   • 它有其他非整数的数字键(例如1.23);
   • 它有其他非正数的整数键(例如0或-12).

"通用表"和数组之间的区别不仅仅是术语的便利.在引擎盖下,Lua实现识别表是否确实是一个数组,并执行一些优化,允许Lua表在使用类似数组的表作为数组时具有高性能(例如,在C中表示).事实上,Lua标准table库假设提供给其函数(例如table.sort)的表确实是数组,并且仅对具有正整数索引的条目进行操作.

考虑到所有这些,我们可以分析您发布的代码中的难点.

a = {}
for n in pairs(t) do
  a[#a + 1] = n 
end

这是一个通用的for循环的例子.pairs返回(除其他外)表迭代函数(因此pairs和ipairs可称为迭代生成函数或迭代发电机).for机器重复调用此迭代器函数以迭代所有键(和相应的值)t.由于只有一个变量出现在for(即n)中,因此t在迭代期间只检索到了键.

a[#a + 1] = n 

只是一种快速的方法来将存储在n表中的密钥附加到表中a,结果证明它是一个数组,因为它在迭代过程中逐步构建,只有从1开始的顺序正整数键.记住这#a是的当前长度a(其最初是0,因为a没有条目),从而a[#a+1]创建具有整数键的新条目#a + 1,而不破坏序列属性的a.

总而言之,该for循环只是收集t数组a中的所有键,以便使用它们进行排序table.sort,然后打印它们:

table.sort(a)
for _, n in ipairs(a) do 
    print (n)
end

前面是另一个通用的例子.在这种情况下,返回的迭代器函数ipairs将返回(正整数)键和a迭代期间的值(按此顺序).由于我们只对打印值感兴趣(键将是1,, 2...等,因为它a是一个数组),我们使用_虚拟变量来获取(对我们无关的)键.我们可以使用另一个名称,但在Lua中使用(完全合法和正常)名称_来完成此任务是惯用的.

分析的定义pairsByKeys有点难以分析.它的目的是让一个迭代器generator(pairsByKeys)返回一个迭代器函数,它可以迭代一个表,保证迭代是根据特定的键顺序完成的(Lua pairs不保证任何特定的迭代顺序).它意味着像这样使用:

for k, v in pairsByKeys( t ) do
    print( k, v )
end

我们来分析一下定义.我们将看到它在单个函数中包含我们已经分析的代码的逻辑(加上增强).

function pairsByKeys(t,f)
    local b = {}
    for x in pairs(t) do
      b[#b + 1] = x
    end
    table.sort(b, f)
    local i = 0
    return function()
      i = i + 1
      return b[i], t[b[i]] 
    end
end

首先要注意的是pairsByKeys返回一个函数(迭代器),它实际上是一个带有三个upvalues(i,t和b)的匿名闭包.这意味着返回的函数将能够在for机器执行时引用这三个变量(此闭包是有状态迭代器的一个示例).

在返回迭代器之前,pairsByKeys"预处理"要迭代的表,t提取其键并按照我们上面已经看到的那样对它们进行排序.因此,b将t按照table.sort(b,f)将它们放置的顺序保存所有键.请注意,此调用table.sort具有附加参数f,该参数是可在调用时指定的比较器函数pairsByKeys.这允许根据不同的标准对键进行排序(这是我告诉你的"增强").

该i变量将持有的关键指标b刚刚遍历.因为在这个阶段没有发生迭代(尚未创建迭代器).

现在让我们关注迭代器函数:

function()
  i = i + 1
  return b[i], t[b[i]] 
end

每当for机器调用它时,它将递增i,然后它将获取b[i],这是下一个要迭代的键(它从b它b保存有关其顺序的信息),然后b[i]再次使用它来获取相应的值t[b[i]]来自原始表t,其中包含此信息.返回键和值,这两个值是(在每次迭代中)分配给循环变量k和v上面示例的值,然后打印它们.