在 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,

这是字符串的地址/计数对数组。如果要访问其中之一，可以按如下方式执行此操作：

: 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并将正确的偏移量添加到您想要的字符串地址/计数中。该偏移量是数组条目(2 个单元格)的大小乘以索引(位于数据堆栈上)。因此，表达式myStringArray swap 2 cells * +.接下来是检索该位置的双字(地址和计数)的2@。

投入使用...

3 myString type array ok
0 myString type This ok

等。。。

既然您已经了解了为数组编制索引的基础知识，那么排序的"最佳实践"将遵循为要排序的数组类型选择排序算法的常规最佳实践。在这种情况下，冒泡排序可能适用于非常小的字符串数组。您可以使用compare单词来比较两个字符串。例如：

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

结果是0意味着字符串相等。

Answer 2

对数组进行排序的最佳实践方法是使用一些现有的库。如果现有的库不符合你的需求，或者你的主要目的是学习—— 那么实现自己的库是有意义的。

使用库

例如，福斯基金会图书馆(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 解决方案，请查看气泡排序示例。

字符串数组应仅包含字符串地址。字符串本身应该保存在另一个地方。在这种情况下，使用计数字符串格式很有用 — 因此，我们使用c"单词表示字符串文字。为了保留字符串本身，我们将初始化代码放入定义中(在本例中:noname) — 它将字符串保留在字典空间中。

气泡排序从数字的变体改编为字符串的变体，只需替换比较项目的单词即可。请注意，2@单词返回顶部最低地址的值。

代码示例

 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