」工欲善其事,必先利其器。「—孔子《論語.錄靈公》
首頁 > 程式設計 > C 中的不相交聯合

C 中的不相交聯合

發佈於2024-11-08
瀏覽:894

Disjoint Unions in C

目前还不清楚如何在 C:
中表达此 Haskell 类型

data Tree = Leaf Int | Inner Tree Tree

与 Haskell 和 Rust 等语言不同,C 缺乏对
的内置支持 不相交联合。然而,如果我们愿意做一些额外的输入,它确实提供了代表它们所需的所有成分。

首先要认识到的是,不相交的并集由以下部分组成:

  • 许多不同的变体
  • 每个都有一些与之关联的数据

在我们的二叉树示例中,我们有两个变体:“叶子”和“内部”。叶变量存储单个整数(其数据),内部变量存储两棵树(代表其左子树和右子树)。

我们可以使用具有两个字段的结构体在 C 中表示这样的动物:

  1. “类型标签”,通常是整数,指示所表示的变体。
  2. A data 字段,用于存储与变体相关的数据。

使用枚举定义不同的变体类型标签很方便:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

存储数据怎么样?这就是工会要解决的问题类型。

工会

联合只是一块能够存储多种不同类型数据的内存。例如,这是一个可以存储 32 位 int 或 5 个字符的数组的联合。

union int_or_chars {
        int num;
        char letters[5];
};

类型为 union int_or_chars 的变量可以在任何特定时间保存 int 或 5 个字符的数组(只是不能同时保存):

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

像 union int_or_chars 这样的联合拥有足够大的内存块可供使用,可以容纳最大的成员。这是显示其工作原理的示意图:

  ----   ----   ----   ----   ----  
| byte |      |      |      |      |
  ----   ----   ----   ----   ----  
||
||

这有助于解释为什么在我们在 quux 中存储字符数组后打印 quux.num 会导致“垃圾”:它不是垃圾,而是字符串“abcd”被解释为整数。 (在我的机器上,quux.num 以十六进制打印为 64636261。字符“a”的 ASCII 值为 0x61,“b”的值为 0x62,“c”为 0x63,“d”为 0x64。由于我的处理器是小端字节序,所以顺序颠倒了。)

关于联合的最后一点,您可能会对 sizeof:
报告的大小感到惊讶

printf("%ld\n", sizeof(union int_or_chars));
// => 8

在我的机器上,类型 union int_or_chars 的大小为 8 个字节,而不是我们预期的 5 个字节。由于我的处理器架构规定的对齐要求,已添加一些填充。

返回二叉树

我们现在准备继续将二叉树类型从 Haskell 转换为 C。我们已经定义了一个枚举来表示变体的类型。现在我们需要一个联合来存储其数据:

union tree_data {
        int leaf;
        struct inner_data inner;
};

其中 struct inner_data 是包含“内部”变体的左右子级的结构:

struct inner_data {
        struct tree *left;
        struct tree *right;
};

请注意,“内部”变体维护指向其左右子节点的指针。间接是必要的,因为否则结构树将没有固定的大小。

这些部分就位后,我们就可以定义我们的树类型了:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

和树玩耍

让我们编写一些函数来构造树:

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

并打印它们:

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

这使我们能够翻译 Haskell 表达式:

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

到 C 中为:

inner(inner(leaf(1), leaf(2)), leaf(3));

例如:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

作为一个稍微有趣的例子,我们来翻译一下这个深度优先搜索函数:

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

使用我们的树类型:

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

这当然更冗长,但翻译过程很简单(编译器大概可以为我们做这种事情......)。

权衡

我们最后稍微离题了一些关于替代表示所涉及的权衡。具体来说,假设代替:

union tree_data {
        int leaf;
        struct inner_data inner;
};

我们使用:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

在第一种情况下,联合体包含一个结构体inner_data,而在第二种情况下,它存储一个指向该结构体的指针。因此,第一个联合体稍大一些,为 16 字节,而我的机器上的指针版本为 8 字节。不幸的是,受影响的不仅仅是内部节点:叶节点使用相同的 16 字节联合,但仅存储单个(4 字节)int。感觉有点浪费。

然而,这并不是故事的全部。每次访问内部节点的左子节点和右子节点时,我们都会为额外的间接寻址付出代价:读取不一定便宜,特别是如果指向的内存未缓存。

我怀疑这里提出的主要方法在大多数情况下是一个更好的起点,并且尝试削减一些字节(白色导致额外的读取)是不值得的,直到它是。

版本聲明 本文轉載於:https://dev.to/wjlewis/disjoint-unions-in-c-4i9i如有侵犯,請聯絡[email protected]刪除
最新教學 更多>
  • C++20 Consteval函數中模板參數能否依賴於函數參數?
    C++20 Consteval函數中模板參數能否依賴於函數參數?
    [ consteval函數和模板參數依賴於函數參數在C 17中,模板參數不能依賴一個函數參數,因為編譯器仍然需要對非contexexpr futcoriations contim at contexpr function進行評估。 compile time。 C 20引入恆定函數,必須在編譯時進...
    程式設計 發佈於2025-07-22
  • Spark DataFrame添加常量列的妙招
    Spark DataFrame添加常量列的妙招
    在Spark Dataframe ,將常數列添加到Spark DataFrame,該列具有適用於所有行的任意值的Spark DataFrame,可以通過多種方式實現。使用文字值(SPARK 1.3)在嘗試提供直接值時,用於此問題時,旨在為此目的的使用column方法可能會導致錯誤。 df.with...
    程式設計 發佈於2025-07-22
  • 為什麼在我的Linux服務器上安裝Archive_Zip後,我找不到“ class \” class \'ziparchive \'錯誤?
    為什麼在我的Linux服務器上安裝Archive_Zip後,我找不到“ class \” class \'ziparchive \'錯誤?
    class'ziparchive'在Linux Server上安裝Archive_zip時找不到錯誤 commant in lin ins in cland ins in lin.11 on a lin.1 in a lin.11錯誤:致命錯誤:在... cass中找不到類z...
    程式設計 發佈於2025-07-22
  • 如何避免Go語言切片時的內存洩漏?
    如何避免Go語言切片時的內存洩漏?
    ,a [j:] ...雖然通常有效,但如果使用指針,可能會導致內存洩漏。這是因為原始的備份陣列保持完整,這意味著新切片外部指針引用的任何對象仍然可能佔據內存。 copy(a [i:] 對於k,n:= len(a)-j i,len(a); k
    程式設計 發佈於2025-07-22
  • eval()vs. ast.literal_eval():對於用戶輸入,哪個Python函數更安全?
    eval()vs. ast.literal_eval():對於用戶輸入,哪個Python函數更安全?
    稱量()和ast.literal_eval()中的Python Security 在使用用戶輸入時,必須優先確保安全性。強大的Python功能Eval()通常是作為潛在解決方案而出現的,但擔心其潛在風險。 This article delves into the differences betwee...
    程式設計 發佈於2025-07-22
  • 如何將PANDAS DataFrame列轉換為DateTime格式並按日期過濾?
    如何將PANDAS DataFrame列轉換為DateTime格式並按日期過濾?
    將pandas dataframe列轉換為dateTime格式示例:使用column(mycol)包含以下格式的以下dataframe,以自定義格式:})指定的格式參數匹配給定的字符串格式。轉換後,MyCol列現在將包含DateTime對象。 date oped filtering > = ...
    程式設計 發佈於2025-07-22
  • 切換到MySQLi後CodeIgniter連接MySQL數據庫失敗原因
    切換到MySQLi後CodeIgniter連接MySQL數據庫失敗原因
    Unable to Connect to MySQL Database: Troubleshooting Error MessageWhen attempting to switch from the MySQL driver to the MySQLi driver in CodeIgniter,...
    程式設計 發佈於2025-07-22
  • Python中何時用"try"而非"if"檢測變量值?
    Python中何時用"try"而非"if"檢測變量值?
    使用“ try“ vs.” if”來測試python 在python中的變量值,在某些情況下,您可能需要在處理之前檢查變量是否具有值。在使用“如果”或“ try”構建體之間決定。 “ if” constructs result = function() 如果結果: 對於結果: ...
    程式設計 發佈於2025-07-22
  • 在UTF8 MySQL表中正確將Latin1字符轉換為UTF8的方法
    在UTF8 MySQL表中正確將Latin1字符轉換為UTF8的方法
    在UTF8表中將latin1字符轉換為utf8 ,您遇到了一個問題,其中含義的字符(例如,“jáuòiñe”)在utf8 table tabled tablesset中被extect(例如,“致電。為了解決此問題,您正在嘗試使用“ mb_convert_encoding”和“ iconv”轉換受...
    程式設計 發佈於2025-07-22
  • FastAPI自定義404頁面創建指南
    FastAPI自定義404頁面創建指南
    response = await call_next(request) if response.status_code == 404: return RedirectResponse("https://fastapi.tiangolo.com") else: ...
    程式設計 發佈於2025-07-22
  • Java中假喚醒真的會發生嗎?
    Java中假喚醒真的會發生嗎?
    在Java中的浪費喚醒:真實性或神話? 在Java同步中偽裝喚醒的概念已經是討論的主題。儘管存在這種行為的潛力,但問題仍然存在:它們實際上是在實踐中發生的嗎? Linux的喚醒機制根據Wikipedia關於偽造喚醒的文章,linux實現了pthread_cond_wait()功能的Linux實現,...
    程式設計 發佈於2025-07-22
  • 為什麼不使用CSS`content'屬性顯示圖像?
    為什麼不使用CSS`content'屬性顯示圖像?
    在Firefox extemers屬性為某些圖像很大,&& && && &&華倍華倍[華氏華倍華氏度]很少見,卻是某些瀏覽屬性很少,尤其是特定於Firefox的某些瀏覽器未能在使用內容屬性引用時未能顯示圖像的情況。這可以在提供的CSS類中看到:。 googlepic { 內容:url(&...
    程式設計 發佈於2025-07-22
  • CSS可以根據任何屬性值來定位HTML元素嗎?
    CSS可以根據任何屬性值來定位HTML元素嗎?
    靶向HTML元素,在CSS 但是,出現一個常見的問題:元素可以根據任何屬性值而定位嗎?本文探討了此主題。 的目標元素有任何任何屬性值,屬性selector可以使用。通過省略屬性名稱之後的值,可以選擇具有該屬性的所有元素。例如:此行為反映默認的光標:使用定義的Href屬性的標記的指針樣式。非空屬性值...
    程式設計 發佈於2025-07-22
  • 如何為PostgreSQL中的每個唯一標識符有效地檢索最後一行?
    如何為PostgreSQL中的每個唯一標識符有效地檢索最後一行?
    postgresql:為每個唯一標識符在postgresql中提取最後一行,您可能需要遇到與數據集合中每個不同標識的信息相關的信息。考慮以下數據:[ 1 2014-02-01 kjkj 在數據集中的每個唯一ID中檢索最後一行的信息,您可以在操作員上使用Postgres的有效效率: id dat...
    程式設計 發佈於2025-07-22
  • 如何實時捕獲和流媒體以進行聊天機器人命令執行?
    如何實時捕獲和流媒體以進行聊天機器人命令執行?
    在開發能夠執行命令的chatbots的領域中,實時從命令執行實時捕獲Stdout,一個常見的需求是能夠檢索和顯示標準輸出(stdout)在cath cath cant cant cant cant cant cant cant cant interfaces in Chate cant inter...
    程式設計 發佈於2025-07-22

免責聲明: 提供的所有資源部分來自互聯網,如果有侵犯您的版權或其他權益,請說明詳細緣由並提供版權或權益證明然後發到郵箱:[email protected] 我們會在第一時間內為您處理。

Copyright© 2022 湘ICP备2022001581号-3