在 Forth 中对字符串数组进行排序

Question

我已经使用 CREATE 创建了一个字符串数组：

create mystringarray s" This" , s" is" , s" a", s" list" ,

我想按升序排序。我在网上找到了一些汇编语言的教程，但我想在 Forth 中完成。最佳实践方法是什么？

Answer 1

您需要首先确保您的数据表示准确。

Forth 中的文字字符串是使用单词 s" 获得的，因此您可以这样写，例如：

s" This"  ok

输入后，如果您执行 .s，您将看到两个值：

.s <2> 7791776 4  ok

这是一个指向实际字符串（字符数组）的指针，以及字符串中字符数的计数。 Forth 中的某些词理解这种字符串表示。 type 就是其中之一。如果您现在输入 type，您将在显示屏上输入字符串：

type This ok

所以现在您知道您需要 两个单元格 来表示由 s" 获得的字符串。您的 create 需要考虑到这一点并使用 2, 词来存储每个条目 2 个单元格，而不是 , 只存储一个单元格：

create myStringArray
    s" This" 2,
    s" is" 2,
    s" an" 2,
    s" array" 2,
    s" of" 2,
    s" strings" 2,

这是一个 address/count 对字符串数组。如果你想访问其中之一，你可以这样做：

: myString ( u1 -- caddr u1 )  \ given the index, get the string address/count
    \ fetch 2 cells from myStringArray + (sizeof 2 cells)*index
    myStringArray swap 2 cells * + 2@ ;

将其分解，您需要获取数组变量 myStringArray 的基数，并向其添加所需字符串 address/count 的正确偏移量。该偏移量是数组条目（2 个单元格）乘以索引（位于数据堆栈上）的大小。因此表达式 myStringArray swap 2 cells * +。接下来是 2@，它检索该位置的双字（地址和计数）。

投入使用...

3 myString type array ok
0 myString type This ok

等...

既然您了解了数组索引的基础知识，那么排序 "best practice" 将遵循为您希望排序的数组类型选择排序算法的正常最佳实践。在这种情况下，冒泡排序可能适用于非常小的字符串数组。 You would use the compare word to compare two strings. 例如：

s" This" 0 myString compare .s <1> 0  ok

结果为 0，表示字符串相等。

Answer 2

排序数组的最佳实践方法是使用一些现有的库。如果现有的库不能满足您的需求，或者您的主要目的是学习 — 那么实现您自己的库就有意义了。

使用库

例如，Cell array module from The Forth Foundation Library (FFL) 可用于对任意项目的数组进行排序。

代码示例

include ffl/car.fs
include ffl/str.fs

0 car-new value arr  \ new array in the heap

\ shortcut to keep -- add string into our 'arr' array
: k ( a1 u1 -- ) str-new dup arr car-push str-set ;

\ set compare method
:noname ( a1 a2 -- n ) >r str-get r> str-get compare ; arr car-compare!

\ dump strings from the array
: dump-arr ( -- ) arr car-length@ 0 ?do i arr car-get str-get type cr loop ;

\ populate the array
s" This" k s" is" k s" a" k s" list" k

\ test sorting
dump-arr cr
arr car-sort 
dump-arr cr

输出

This
is
a
list

This
a
is
list

使用裸 Forth

如果您只是为了学习而需要一个简单的 Forth 解决方案，请查看 bubble sort sample。

字符串数组应该只包含字符串地址。字符串本身应该保存在其他地方。在这种情况下使用计数字符串格式很有用——因此，我们使用 c" 字作为字符串文字。为了保留字符串本身，我们将初始化代码放入定义中（在本例中为 :noname）——它将把字符串保留在字典 space 中。

冒泡排序从数字的变体改编为字符串的变体，只是替换了比较项的单词。注意2@ 字returns 最低地址在最上面的值。

代码示例

\ some helper words
: bounds ( addr1 u1 -- addr1 addr2 ) over + swap ;
: lt-cstring ( a1 a2 -- flag ) >r count r> count compare -1 = ;

\ create an array of counted strings
:noname ( -- addr cnt )
  here
    c" This" , c" is" , c" a" , c" list" ,
  here over - >cells
; execute constant cnt constant arr

\ dump strings from the array  
: dump-arr ( -- ) cnt 0 ?do i cells arr + @ count type cr loop ;

\ bubble sort
: sort-arr ( -- )
  cnt 2 u< if exit then
  cnt 1 do true
    arr cnt i - cells bounds do
      i 2@ ( a2 a1 ) lt-cstring if i 2@ swap i 2! false and then
    cell +loop
    if leave then
  loop
;

\ test sorting
dump-arr cr
sort-arr
dump-arr cr

\ the output is the same as before

在 Forth 中对字符串数组进行排序

Sorting an array of strings in Forth

sorting

forth

gforth

使用库

代码示例

使用裸 Forth

代码示例